Гарри Хомяк
Гарри Хомяк живет в гигантской клетке. Внутри клетки находится набор из n пластиковых шариков, соединенных однонаправленными трубками различной длины. Гарри в настоящее время находится в шаре s, а его кровать в шаре t.
Будучи простым хомяком, половинки мозга Гарри не так хороши в общении друг с другом и имеют собственный разум. Левая половина мозга Гарри обычно активная, когда он находится в колесе, и любит бежать как можно дольше. Правая половина Гарри, редко бывающая вообще активной, хотела бы заснуть как можно скорее. Вместе мозговые половинки Гарри будут перемещать его через Лабиринт трубок, в каждом шаре решая по какой из исходящих трубок следовать.
Половинки мозга Гарри очень устают после принятия решения, а затем им нужно немного отдохнуть, чтобы они не могли принять два решения подряд. Таким образом, они принимают решение о том, какую трубку использовать в чередующихся поворотах, при этом левая половина мозга идет первой. Таким образом, начиная с шара s, левая половина мозга Гарри определится с трубкой, которой будет следовать, заканчивая некоторым шаром u, где левая половина мозга Гарри будет отдыхать, а правая половина мозга Гарри выберет исходящую трубку и так далее.
Половинки мозга знакомы со всей клеткой хомяка и могут планировать произвольно далеко вперед. Предполагая, что обе половины мозга принимают оптимальные решения, сколько времени понадобится Гарри, чтобы добраться до своей кровати? Гарантируется, что в каждом шаре есть хотя бы одна выходящая трубка, кроме шара, в котором находится кровать Гарри (там Гарри легко успокоится). Нет труб, соединяющих шар с самим собой, но может быть несколько трубок, идущих от одного шара к другому.
Входные данные
Первая строка содержит четыре целых числа: количество пластиковых шаров n (1 ≤ n ≤ 10^5), количество трубок m (0 ≤ m ≤ 2 * 10^5), местоположение Гарри и его кровати s, t (0 ≤ s, t < n).
Далее следуют m строк, каждая содержит три целых числа описывающих одну трубку: стартовый шар a[i] (0 ≤ a[i] < n), конечный шар b[i] (0 ≤ b[i] < n) и время перехода w[i] (1 ≤ w[i] ≤ 10^4). Обратите внимание, что по каждой трубке можно перемещатьтя только в одном направлении.
Выходные данные
Выведите время, за которое Гарри доберется до своей кровати, или строку infinity, если Гарри обречен бродить по трубам вечно.