Гаррі Хом'ячок#9885
Хом'ячок Гаррі живе у величезній хом'ячій клітці. Усередині клітки знаходяться пластикових куль, з'єднаних односторонніми хом'ячими трубами різної довжини. Зараз Гаррі знаходиться в кулі , а його ліжко — в кулі .
Гаррі — простий хом'ячок, і дві півкулі його мозку не дуже добре ладнають одна з одною: кожна з них має свою думку. Ліва півкуля, зазвичай активна, коли Гаррі біжить у колесі, хоче бігати якомога довше. Права півкуля, яка взагалі рідко буває активною, хоче якомога швидше лягти спати. Разом півкулі скеровують Гаррі лабіринтом труб, вирішуючи в кожній кулі, якою вихідною трубою рухатися далі.
Прийняття рішення дуже втомлює, тому після кожного рішення півкулі потрібно трохи відпочити, і вона не може прийняти два рішення поспіль. Тому півкулі обирають трубу по черзі, і першою ходить ліва півкуля. Починаючи в кулі , ліва півкуля обирає трубу, яка приводить Гаррі до деякої кулі . Там ліва півкуля відпочиває, а права обирає наступну вихідну трубу, і так далі.
Як не дивно, обидві півкулі знають всю клітку і можуть планувати як завгодно далеко наперед. За який час Гаррі дістанеться до ліжка, якщо обидві півкулі діють оптимально? Гарантується, що з кожної кулі виходить хоча б одна труба, окрім кулі з ліжком Гаррі, з якої не виходить жодної (там Гаррі може спокійно відпочити). Жодна труба не з'єднує кулю саму із собою, але з однієї кулі в іншу може вести декілька труб.
У першому рядку задано чотири цілих числа: кількість пластикових куль n~(1 \le n \le 10^5), кількість труб m~(0 \le m \le 2 \cdot 10^5), а також кулі та t~(0 \le s, t < n), в яких знаходяться Гаррі та його ліжко.
Кожен з наступних рядків містить три цілих числа, що описують трубу: кулю a_i~(0 \le a_i < n), в якій труба починається, кулю b_i~(0 \le b_i < n), в якій вона закінчується, та час w_i~(1 \le w_i \le 10^4), необхідний для її проходження. Кожною трубою можна рухатися тільки в одному напрямку.
Виведіть час, за який Гаррі дістанеться до свого ліжка, або рядок infinity, якщо Гаррі приречений вічно блукати трубами.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
Приклад 5