{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThe 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.\u003cbr\u003e\u003cbr\u003eTaku 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.\u003cbr\u003e\u003cbr\u003eFirst 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:\u003cbr\u003e\u003cbr\u003eIf 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 \u003cb\u003eminimum\u003c/b\u003e 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.\u003cb\u003eFor 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\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eThis magic brings much difficulty for Taku, that\u0027s why a second magic comes to help.\u003cbr\u003e\u003cbr\u003eThe 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\u0027t use it until he has used the first magic \u003cb\u003econtinuously\u003c/b\u003e for at least K times.\u003cbr\u003e\u003cbr\u003eTwo 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$.\u003cbr\u003e\u003cbr\u003eFor each road, the mana cost is given to Taku, which is same for both kinds of magic.\u003cbr\u003e\u003cbr\u003eNow Taku wonders the \u003cb\u003eminimum\u003c/b\u003e time he needs to move from city $1$ to city $N$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"First line contains an integer $T$, which indicates the number of test cases.\u003cbr\u003e\u003cbr\u003eEvery 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.\u003cbr\u003e\u003cbr\u003eThe following $M$ lines describe the rods as format \u0027$u \\ v\\ w$\u0027, which indicates there is a road between city $u$ and city $v$, and its mana cost is $w$.\u003cbr\u003e\u003cbr\u003e$1 \\leq T \\leq 100$.\u003cbr\u003e\u003cbr\u003efor 85% data, $1 \\leq N \\leq 10$, $1 \\leq M \\leq 20$ and $0 \\leq K \\leq 10$.\u003cbr\u003e\u003cbr\u003efor 100% data, $1 \\leq N, M \\leq 10^5$ and $0 \\leq K \\leq 10^5$.\u003cbr\u003e\u003cbr\u003e$1 \\leq u, v \\leq N$.\u003cbr\u003e\u003cbr\u003e$1 \\leq w \\leq 10^5$.\u003cbr\u003e\u003cbr\u003eFor every city, the mana cost of all roads connected with it are different."}},{"title":"Output","value":{"format":"HTML","content":"For every test case, you should output \u0027Case #x: y\u0027,\u003cbr\u003ewhere $x$ indicates the case number and counts from $1$, and $y$ is the\u003cbr\u003eminimum time he needs to move from city $1$ to city $N$. \u003cbr\u003eif Taku can\u0027t move to city $N$, y is -1."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 2 2\r\n1 2 1\r\n1 3 4\r\n5 5 1\r\n1 2 1\r\n2 3 2\r\n3 4 3\r\n2 4 4\r\n4 5 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1\r\nCase #2: 4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eFor 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\u0027t use second magic at city 4 immediately\u003cbr\u003e"}}]}