13394번 - 여행

N개의 도시로 이루어진 나라가 있다. 이 나라의 도시는 1번부터 N번까지 번호가 매겨져 있다. 이 나라에는 두 도시를 연결하는 양방향 도로가 M개 존재한다.

현정이는 이 나라를 도로를 이용해서 여행하려고 한다. 현정이는 도시를 좋아하지 않기 때문에, 도시에서 머무는 경우는 없다. 같은 도시를 여러 번 방문할 수 있으며, 같은 도시도 여러 번 이용할 수 있다.

지금 현정이는 1번 도시에 있다. T분 후에 N번 도시에 있을 수 있는지 없는지 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 개수 N과 도로의 개수 M, 그리고 시간 제한 T가 주어진다. (2 ≤ N ≤ 50, 1 ≤ M ≤ 50, 1 ≤ T ≤ 10¹⁸)

둘째 줄부터 M개의 줄에 도로의 정보가 주어진다. 도로의 정보는 u, v, w 형식이며, u와 v를 연결하는 도로이고, 이동하는데 w분이 걸린다는 의미이다. 같은 도로가 두 번 이상 주어지는 경우는 없으며, u와 v는 항상 다르다. (1 ≤ w ≤ 10,000)

T분 후에 도시 N에 있을 수 있으면 1, 없으면 0을 출력한다.

예제 1의 경우에 1번 -> 2번 -> 3번으로 이동하면 된다.

예제 2의 경우에 1번 -> 3번 -> 2번 -> 1번 -> 3번으로 이동하면 된다.