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

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

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

입력 형식

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

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

출력 형식

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

예제 입력 1

3 3 11
1 3 7
1 2 6
2 3 5

예제 출력 1

1

예제 입력 2

3 3 25
1 3 7
1 2 6
2 3 5

예제 출력 2

1

예제 입력 3

2 1 9
1 2 1

예제 출력 3

1

예제 입력 4

2 1 1000000000000000000
2 1 1

예제 출력 4

0

예제 입력 5

4 3 1000
1 3 10
1 2 10
2 3 10

예제 출력 5

0

힌트

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

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