E. Bugcat's Gathering
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Two Bugcats are planning to meet up for a gathering. The map they live on consists of $$$n$$$ nodes and $$$m$$$ directed edges. The first Bugcat starts at Node $$$1$$$, and the second Bugcat starts at Node $$$n$$$.

Each edge $$$i$$$ connects node $$$x_i$$$ to node $$$y_i$$$. There are two ways to traverse an edge:

  • Walking: This consumes $$$z_i$$$ units of stamina.
  • Taking a Taxi: This costs $$$1$$$ dollar but consumes $$$0$$$ stamina.

The two Bugcats have a combined total budget of $$$w$$$ dollars. They can choose to take a taxi on any edge at any time, provided they do not exceed their total budget.

Your task is to find the minimum total stamina the two Bugcats must consume in order to meet at the same node, given their budget constraint.If it is impossible for the two Bugcats to meet, output $$$-1$$$.

Input

The input uses multiple test cases.

The first line contains an integer $$$T$$$, the number of test cases.

For each test case, the first line contains three integers $$$n, m, w$$$ ($$$\sum n, \sum m \le 1000, 0 \le w \le 1000$$$), representing the number of nodes, the number of edges, and the total budget.

The next $$$m$$$ lines each contain three integers $$$x_i, y_i, z_i$$$ ($$$1 \le x_i, y_i \le n, 1 \le z_i \le 10^9$$$), representing a directed edge from $$$x_i$$$ to $$$y_i$$$ with a walking stamina cost of $$$z_i$$$.

Output

For each test case, output a single line representing the minimum combined stamina required for the two Bugcats to meet.If it is impossible for the two Bugcats to meet, output $$$-1$$$.

Example
Input
2
5 5 2
1 2 3
1 3 4
5 4 2
4 3 1
2 3 100
5 4 2
1 2 3
1 3 4
5 4 2
2 3 100
Output
1
-1