Гаррі Хом'як
Гаррі Хом'як мешкає у величезній клітці. Всередині клітки розташовано набір із 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, якщо Гаррі приречений блукати по трубах вічно.