테스트 케이스 조정

당신은 프로그래밍 대회의 심사위원입니다. 최소 비용 경로의 비용을 구하는 그래프 문제의 데이터셋을 준비하고 있습니다. 무작위로 몇 가지 케이스를 생성했지만 그다지 흥미롭지 않습니다. 그래서 정답이 원하는 값(예를 들어 올해를 나타내는 2010 같은 수)이 되도록 데이터셋을 만들고 싶습니다. 이를 위해 일부 간선의 비용을 바꿔서 최소 비용 경로의 비용을 원하는 값으로 조정(tweak)하려 합니다. 이때 바꾸는 간선의 수는 가능한 한 적어야 합니다.

음이 아닌 정수 $c$와 방향 그래프 $G$가 주어집니다. $G$의 각 간선에는 음이 아닌 정수 비용이 붙어 있습니다. $G$의 한 정점에서 다른 정점으로 가는 경로가 주어지면, 그 경로의 비용은 경로를 이루는 간선들의 비용의 합으로 정의합니다. 두 정점의 쌍에 대해서는, 두 정점을 잇는 모든 경로의 비용 중 최솟값을 그 쌍의 최소 비용으로 정의합니다.

그래프와 그 안의 두 정점, 즉 시작 정점인 $1$번 정점과 도착 정점인 $n$번 정점이 주어질 때, 간선들의 비용을 조정하여 정점 $1$에서 정점 $n$으로 가는 최소 비용 경로가 정확히 목표 비용 $c$가 되도록 만들어야 합니다. $c$는 원래 그래프에서 이 두 정점 사이 최소 비용 경로의 비용보다 작다고 가정할 수 있습니다.

예를 들어 그림 G.1에서, 주어진 그래프에서 정점 1에서 정점 3으로 가는 최소 비용은 6입니다. 이 최소 비용을 2로 맞추려면, 정점 1에서 정점 3으로 가는 간선의 비용을 2로 바꾸면 됩니다. 그러면 변경 후에는 이 직접 간선이 최소 비용 경로가 됩니다.

또 다른 예로 그림 G.2에서, 정점 1에서 정점 12로 가는 최소 비용은 4022입니다. 이 최소 비용을 2010으로 맞추려면, 정점 6에서 정점 12로 가는 간선과 그래프 오른쪽 절반에 있는 여섯 간선 중 하나를 바꾸면 됩니다. 간선을 바꾸는 방법은 여러 가지가 있지만, 바꾸는 간선의 최소 개수는 2입니다.

그림 G.1: 그래프 예시 1

그림 G.2: 그래프 예시 2

입력은 여러 개의 데이터셋으로 이루어집니다. 각 데이터셋의 형식은 다음과 같습니다.

n m c
f1 t1 c1
f2 t2 c2
.
.
.
fm tm cm

정수 $n$, $m$, $c$는 각각 정점의 수, 간선의 수, 목표 비용이며, 하나의 공백으로 구분됩니다. 여기서 $2 \le n \le 100$, $1 \le m \le 1000$, $0 \le c \le 100000$입니다.

그래프의 각 정점은 $1$부터 $n$까지의 정수로 표현됩니다.

이어지는 $m$개의 줄은 간선을 나타냅니다. 정수 $f_i$, $t_i$, $c_i$ ($1 \le i \le m$)는 각각 $i$번째 간선의 시작 정점, 도착 정점, 비용이며, 하나의 공백으로 구분됩니다. 이들은 $1 \le f_i, t_i \le n$과 $0 \le c_i \le 10000$을 만족합니다. 또한 $f_i \ne t_i$이고, $i = j$일 때 $(f_i, t_i) \ne (f_j, t_j)$입니다.

각 데이터셋에서 정점 $1$에서 정점 $n$으로 가는 경로가 적어도 하나 존재하며, 원래 그래프에서 정점 $1$에서 정점 $n$으로 가는 최소 비용 경로의 비용은 $c$보다 크다고 가정할 수 있습니다.

입력의 끝은 하나의 공백으로 구분된 세 개의 $0$이 있는 줄로 표시됩니다.

각 데이터셋에 대해, 정점 $1$에서 정점 $n$으로 가는 최소 비용 경로의 비용을 목표 비용 $c$와 같게 만들기 위해 비용을 바꿔야 하는 간선의 최소 개수를 한 줄에 출력하세요. 간선의 비용은 음수가 될 수 없습니다. 출력에는 그 밖의 다른 문자가 포함되어서는 안 됩니다.