Journey of Taku

The Kingdom of Frog has $N$ cities connected by $M$ bidirectional roads. The famous frog magician, Taku, lives in city $1$ and wants to move to city $N$ to meet a friends. Interesting enough, each road has the same length, but possibly has different mana cost.

Taku is old and moving on foot means too much for him. So when moving from one city to another, he can only use magic. There are two kinds of magic he can choose from.

First magic, is the basic magic. This magic can be used at any city at any time. However, it has a shortage. At each city it automatically choose the next city to move using a special rule. Here is how the rule is realized:

If Taku is currently in city $x$, the next city to move will directly depend on the previous city (say $p_x$) Taku comes from, and the mana $w$ it costs to move from $p_x$ to $x$. (Specially, for the first step of the journey, the previous city is $x$ itself (where Taku lives in), and the mana cost is $0$). Then the next city will be chosen from all the neighbouring cities of $x$, except $p_x$. Among those cities, each city will cost Taku some mana to move. The magic will choose the target city as the one that has the mana-cost most close to $w$, if there are multiple choices, the city with the minimum id will be chosen. If there are no possible cities to move, the magic will bring Taku back to $px$, where he just comes from.For every city, the mana cost of all roads connected with it are different and the city of all roads connected with it are different, and there are no road connect to the city itself

This magic brings much difficulty for Taku, that's why a second magic comes to help.

The second magic can give Taku the freedom to choose next city to move, as long as it is neighbouring to the current city. Taku cannot use the second magic too frequently, after using the second magic once, Taku can't use it until he has used the first magic continuously for at least K times.

Two kinds of magic share the same moving speed, since all the roads are of same length, you can assume the time cost for each road is $1$.

For each road, the mana cost is given to Taku, which is same for both kinds of magic.

Now Taku wonders the minimum time he needs to move from city $1$ to city $N$.

First line contains an integer $T$, which indicates the number of test cases.

Every test case begins with three integers $N$, $M$ and $K$, which indicates the numbers of cities, the number of roads and the meaning of $K$ is described in the description.

The following $M$ lines describe the rods as format '$u \ v\ w$', which indicates there is a road between city $u$ and city $v$, and its mana cost is $w$.

$1 \leq T \leq 100$.

for 85% data, $1 \leq N \leq 10$, $1 \leq M \leq 20$ and $0 \leq K \leq 10$.

for 100% data, $1 \leq N, M \leq 10^5$ and $0 \leq K \leq 10^5$.

$1 \leq u, v \leq N$.

$1 \leq w \leq 10^5$.

For every city, the mana cost of all roads connected with it are different.

For every test case, you should output 'Case #x: y',
where $x$ indicates the case number and counts from $1$, and $y$ is the
minimum time he needs to move from city $1$ to city $N$.
if Taku can't move to city $N$, y is -1.

2
3 2 2
1 2 1
1 3 4
5 5 1
1 2 1
2 3 2
3 4 3
2 4 4
4 5 5

Case #1: 1
Case #2: 4

For the second sample case, Taku should move from 1 → 2 → 3 → 4 using first magic, and 4 → 5 using second magic, total time is 4, notice that if Taku using second magic at city 2 and move to city 4, then the next city will be 3 because K is 1 and Taku can't use second magic at city 4 immediately

2015ACM/ICPC亚洲区上海站-重现赛（感谢华东理工）