퍼레이드

JOI 왕국에서는 JOIG 개최를 기념해 고적대 퍼레이드를 열기로 했다.

JOI 왕국에는 N개의 도시가 있고 1부터 N까지 번호가 붙어 있다. 또 고적대가 지나갈 수 있는 일방통행 도로가 M개 있고 1부터 M까지 번호가 붙어 있다. 도로 i(1 ≦ i ≦ M)는 도시 Ai에서 도시 Bi로 향하는 일방통행 도로이며 길이는 Ci이다.

퍼레이드에서 고적대는 다음 조건을 만족하도록 이동해야 한다.

• 도시 1을 출발해 여러 도로를 진행 방향으로 따라 이동하는 것을 반복하며 도시 N으로 향한다.
• 고적대가 지나는 도로 길이의 합은 L 이하이다.

JOI 왕국의 여왕인 당신은 이 조건을 만족하는 고적대의 이동 경로가 없을 수도 있다는 것을 깨달았다. 그래서 퍼레이드를 열기 위해 퍼레이드 당일 0개 이상의 도로의 진행 방향을 뒤집기로 했다.

혼란을 피하기 위해 되도록 진행 방향을 뒤집는 도로 수를 적게 하고 싶다.

JOI 왕국의 도시와 도로 정보, 정수 L이 주어졌을 때, 몇 개의 도로의 진행 방향을 뒤집어 퍼레이드를 열 수 있는지 판정하고, 열 수 있다면 퍼레이드를 열기 위해 필요한 진행 방향을 뒤집는 도로 수의 최솟값을 출력하라.

입력은 다음 형식으로 표준 입력에서 주어진다.

N M L
A1 B1 C1
A2 B2 C2
:
AM BM CM

표준 출력에 퍼레이드를 열기 위해 필요한 진행 방향을 뒤집는 도로 수의 최솟값을 1행으로 출력하라. 단, 어떻게 도로의 진행 방향을 뒤집어도 퍼레이드를 열 수 없는 경우에는 -1을 출력하라.

• 2 ≦ N ≦ 1 000.
• 0 ≦ M ≦ 1 000.
• 1 ≦ L ≦ 1 000 000 000.
• 1 ≦ Ai ≦ N (1 ≦ i ≦ M).
• 1 ≦ Bi ≦ N (1 ≦ i ≦ M).
• Ai ≠ Bi (1 ≦ i ≦ M).
• (Ai, Bi) ≠ (Aj, Bj) (1 ≦ i < j ≦ M).
• 1 ≦ Ci ≦ 1 000 000 (1 ≦ i ≦ M).
• 입력되는 값은 모두 정수이다.