문제

거울세계 [출처: 메이플스토리]

오늘은 알파와 베타가 데이트하는 날이다. 둘은 현재 원래 세계의 제로의 신전에 있고, 루디브리엄으로 가려고 한다.

메이플 월드는 \(N\)개의 지역과 두 지역을 연결하는 \(M\)개의 길로 표현할 수 있다. 각 지역은 \(1\)부터 \(N\)까지 번호가 매겨져 있고, \(1\)번 지역이 제로의 신전이고, \(N\)번 지역이 루디브리엄이다.

길은 한쪽에서 다른 한쪽으로만 이동할 수 있는 일방통행로이다. 그래서 루디브리엄에 도착하지 못할 수도 있다. 대신 알파와 베타는 \(T\)초 만큼의 시간을 들여 원래 세계의 지역에서 거울 세계의 지역으로 이동할 수 있다. 길 위에서는 거울 세계로 이동할 수 없다.

거울 세계는 원래 세계와 같은 \(N\)개의 지역과, 원래 세계와 이동 방향이 반대인 \(M\)개의 길로 표현할 수 있다. 한번 거울 세계로 이동하면 다시 원래 세계로 돌아올 수 없으며, 거울 세계의 루디브리엄에 도착해도 루디브리엄에 도착한 것으로 간주한다.

알파와 베타가 루디브리엄에 도착하는 최소 소요 시간을 구하는 프로그램을 작성해 보자.

입력

첫째 줄에 \(N(2\le N \le 100\, 000)\), \(M(1 \le M \le 300\, 000)\), \(T(0 \le T \le 100\,000)\)가 공백으로 구분되어 주어진다.

둘째 줄부터 \(M\)개의 줄에 걸쳐 길 정보가 \(u\ v\ w(1\le u, v\le N; u\ne v; 1\le w\le 1\,000\, 000)\)의 형태로 주어진다. \(u\) 지역에서 \(v\) 지역으로 가는 길이 존재하며, 이동하는데 \(w\)초가 소요된다는 의미다.

출력

알파와 베타가 루디브리엄에 도착하는 최소 소요 시간을 초 단위로 출력한다. 만약 루디브리엄에 도착하는 것이 불가능하다면 대신 -1 을 출력한다.

예제 입력 1

4 4 8
1 2 1
2 4 10
4 3 1
3 1 1

예제 출력 1

10

원래 세계의 제로의 신전(\(1\)번 지역)에서 거울 세계의 제로의 신전으로 이동한다. \(8\)초가 소요된다.

거울 세계의 제로의 신전에서 거울 세계의 \(3\)번 지역으로 이동한다. \(1\)초가 소요된다.

거울 세계의 3번 지역에서 거울 세계의 루디브리엄(\(4\)번 지역)으로 이동한다. \(1\)초가 소요된다.

따라서 총 \(10\)초가 소요되며, 이보다 더 빠르게 도착하는 경우는 존재하지 않는다.

예제 입력 2

4 3 5
1 2 3
3 2 4
3 4 5

예제 출력 2

-1

예제 입력 3

7 9 0
5 2 8
3 4 2
5 3 3
4 1 10
6 4 2
1 5 5
2 7 10
7 6 3
1 2 10

예제 출력 3

15

힌트

답이 너무 커질 수도 있으므로 4바이트 정수형(int)이 아니라, 8바이트 정수형(C/C++: long long int, Java: long)을 사용하도록 하자.