문제

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

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

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

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

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

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

입력

첫째 줄에 $N(2≤ N ≤ 100\, 000)$, $M(1 ≤ M ≤ 300\, 000)$, $T(0 ≤ T ≤ 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)을 사용하도록 하자.