햄스터 해리

햄스터 해리는 거대한 햄스터 케이지에 살고 있다. 케이지 안에는 n개의 플라스틱 공이 있고, 길이가 제각각인 단방향 햄스터 튜브로 연결되어 있다. 해리는 현재 공 s에 있고, 침대는 공 t에 있다.

단순한 햄스터인 해리의 좌뇌와 우뇌는 서로 소통을 잘 하지 못하고 각자 제멋대로다. 해리가 햄스터 휠 안에 있을 때 주로 활동하는 좌뇌는 최대한 오래 달리고 싶어 한다. 거의 활동하지 않는 우뇌는 최대한 빨리 잠들고 싶어 한다. 두 뇌는 함께 해리를 튜브 미로 사이로 안내하며, 각 공에서 어떤 나가는 튜브를 따라갈지 결정한다.

두 뇌는 결정을 내리면 몹시 피곤해져서 잠시 쉬어야 하므로 연달아 두 번 결정할 수 없다. 따라서 두 뇌는 어떤 튜브를 탈지 번갈아 가며 결정하고, 좌뇌가 먼저 시작한다. 공 s에서 시작하면 좌뇌가 따라갈 튜브를 정해 어떤 공 u에 도착하고, 그곳에서 좌뇌가 쉬는 동안 우뇌가 나가는 튜브를 고르는 식이다.

직관과 달리 두 뇌는 햄스터 케이지 전체를 알고 있으며 얼마든지 멀리까지 내다보고 계획을 세울 수 있다. 두 뇌가 모두 최적으로 결정한다고 가정할 때, 해리가 침대에 도달하는 데 걸리는 시간은 얼마인가? 해리의 침대가 있는 공을 제외한 각 공에는 나가는 튜브가 적어도 하나 있음이 보장된다. 침대가 있는 공에는 나가는 튜브가 없다. 자기 자신으로 향하는 튜브는 없지만, 한 공에서 다른 공으로 가는 튜브가 여러 개 있을 수 있다.

• 첫째 줄에 공백으로 구분된 네 정수가 주어진다: 플라스틱 공의 수 1 ≤ n ≤ 105, 튜브의 수 0 ≤ m ≤ 2 · 105, 해리와 침대의 위치 0 ≤ s, t < n.
• 이어서 m개의 줄이 주어지며, 각 줄에는 튜브 하나를 설명하는 공백으로 구분된 세 정수가 있다: 튜브가 시작하는 공 0 ≤ ai < n, 끝나는 공 0 ≤ bi < n, 지나는 데 걸리는 시간 1 ≤ wi ≤ 104. 각 튜브는 한 방향으로만 지날 수 있다.

해리가 침대에 도달하는 데 걸리는 시간을 출력한다. 해리가 영원히 튜브를 떠돌 운명이라면 문자열 infinity를 출력한다.