여행

N개의 도시로 이루어진 나라가 있다. 도시에는 1번부터 N번까지 번호가 붙어 있고, 두 도시를 잇는 양방향 도로가 M개 있다.

현정이는 도로를 이용해 이 나라를 여행하려고 한다. 현정이는 도시를 좋아하지 않아서 도시에 머무르는 일이 없다. 같은 도시를 여러 번 방문해도 되고, 같은 도로를 여러 번 지나가도 된다.

지금 현정이는 1번 도시에 있다. 정확히 T분 뒤에 N번 도시에 있을 수 있는지 판정하는 프로그램을 작성하시오.

첫째 줄에 도시의 개수 N, 도로의 개수 M, 시간 T가 주어진다. ($2 \le N \le 50$, $1 \le M \le 50$, $1 \le T \le 10^{18}$)

둘째 줄부터 M개의 줄에 도로의 정보가 u, v, w 형식으로 주어진다. u번 도시와 v번 도시를 잇는 도로이고, 지나가는 데 w분이 걸린다는 뜻이다. 같은 도로가 두 번 이상 주어지지 않으며, u와 v는 항상 다르다. ($1 \le w \le 10000$)

정확히 T분 뒤에 N번 도시에 있을 수 있으면 1, 없으면 0을 출력한다.