Гарри Хомяк живет в гигантской клетке. Внутри клетки находится набор из n пластиковых шариков, соединенных однонаправленными трубками различной длины. Гарри в настоящее время находится в шаре s, а его кровать в шаре t.

Будучи простым хомяком, половинки мозга Гарри не так хороши в общении друг с другом и имеют собственный разум. Левая половина мозга Гарри обычно активная, когда он находится в колесе, и любит бежать как можно дольше. Правая половина Гарри, редко бывающая вообще активной, хотела бы заснуть как можно скорее. Вместе мозговые половинки Гарри будут перемещать его через Лабиринт трубок, в каждом шаре решая по какой из исходящих трубок следовать.

Половинки мозга Гарри очень устают после принятия решения, а затем им нужно немного отдохнуть, чтобы они не могли принять два решения подряд. Таким образом, они принимают решение о том, какую трубку использовать в чередующихся поворотах, при этом левая половина мозга идет первой. Таким образом, начиная с шара s, левая половина мозга Гарри определится с трубкой, которой будет следовать, заканчивая некоторым шаром u, где левая половина мозга Гарри будет отдыхать, а правая половина мозга Гарри выберет исходящую трубку и так далее.

Половинки мозга знакомы со всей клеткой хомяка и могут планировать произвольно далеко вперед. Предполагая, что обе половины мозга принимают оптимальные решения, сколько времени понадобится Гарри, чтобы добраться до своей кровати? Гарантируется, что в каждом шаре есть хотя бы одна выходящая трубка, кроме шара, в котором находится кровать Гарри (там Гарри легко успокоится). Нет труб, соединяющих шар с самим собой, но может быть несколько трубок, идущих от одного шара к другому.

Входные данные

Первая строка содержит четыре целых числа: количество пластиковых шаров n (1 ≤ n ≤ 105), количество трубок m (0 ≤ m ≤ 2 * 105), местоположение Гарри и его кровати s, t (0 ≤ s, t < n).

Далее следуют m строк, каждая содержит три целых числа описывающих одну трубку: стартовый шар ai (0 ≤ ai < n), конечный шар bi (0 ≤ bi < n) и время перехода wi (1 ≤ wi ≤ 104). Обратите внимание, что по каждой трубке можно перемещатьтя только в одном направлении.

Выходные данные

Выведите время, за которое Гарри доберется до своей кровати, или строку infinity, если Гарри обречен бродить по трубам вечно.