부스터

밥은 매일 집에서 사무실로 출근한다. 집과 사무실이 멀리 떨어져 있어서 여러 구역을 지나야 하고, 밥은 구역 사이의 도로망이 그려진 지도를 보고 늘 가장 빠른 길로 다닌다. 그런데 어느 날 교통 체증에 걸려 지각하고 말았다. 상사는 한 번 더 늦으면 해고하겠다고 경고했다. 그날 이후 밥은 밤낮으로 그 걱정에 시달린다.

사정을 아는 앨리스가 밥의 차에 쓸 부스터를 만들어 주었다. 부스터를 켜면 차가 두 배로 빨라지지만, 차가 방향을 틀거나 속도를 줄이면 부스터는 곧바로 멈춘다. 그래서 부스터 하나는 도로 하나에만 쓸 수 있고, 그 도로를 지나고 나면 다 쓴 것이 된다. 한 도로에 부스터를 두 개 이상 겹쳐 쓸 수는 없다. 이동 시간이 $T$분인 도로에 부스터를 쓰면 그 도로를 지나는 데 $\lfloor T/2 \rfloor$분이 걸린다.

오늘 교통 상황은 최악이다. 밥에게는 부스터가 $K$개 있고, 그중 몇 개만 써도 되고 전부 다 써도 된다. 집은 1번 구역, 사무실은 $N$번 구역이다. 부스터를 하나도 쓰지 않았을 때의 최단 이동 시간에서, 부스터를 가장 잘 배치했을 때의 최단 이동 시간을 뺀 값을 구하자. 오늘 밥이 최대 몇 분을 아낄 수 있는지 묻는 문제다.

첫 줄에 테스트 케이스의 개수 $C$가 주어진다.

각 테스트 케이스의 첫 줄에는 구역의 수 $N$, 도로의 수 $M$, 밥이 가진 부스터의 수 $K$가 주어진다 ($1 \le N \le 5\,000$, $1 \le M \le 100\,000$, $1 \le K \le 100$).

다음 $M$개 줄에는 도로 하나의 정보가 정수 $X$, $Y$, $T$로 주어진다 ($1 \le X, Y \le N$, $2 \le T \le 100\,000$). 이 도로는 $X$번 구역과 $Y$번 구역을 잇고, 지나는 데 $T$분이 걸린다. 모든 도로는 양방향이라 밥은 어느 쪽으로든 지날 수 있다. 같은 구역 쌍을 잇는 도로가 두 개 이상 주어지는 경우는 없다. 1번 구역에서 $N$번 구역으로 가는 경로는 항상 존재한다.

테스트 케이스마다 한 줄에 정수 하나를 출력한다. 부스터를 최대 $K$개까지 써서 아낄 수 있는 시간의 최댓값, 즉 부스터를 쓰지 않은 최단 이동 시간에서 부스터를 써서 얻을 수 있는 가장 짧은 이동 시간을 뺀 값이다.