{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere are $N$ cities in the country, and $M$ directional roads from $u$ to $v(1\\le u, v\\le n)$. Every road has a distance $c_i$. Haze is a Magical Girl that lives in City $1$, she can choose no more than $K$ roads and make their distances become $0$. Now she wants to go to City $N$, please help her calculate the minimum distance.\u003c/p\u003e\u003ch3\u003eInput\u003c/h3\u003e\u003cp\u003eThe first line has one integer $T(1 \\le T\\le 5)$, then following $T$ cases.\u003c/p\u003e\u003cp\u003eFor each test case, the first line has three integers $N, M$ and $K$.\u003c/p\u003e\u003cp\u003eThen the following $M$ lines each line has three integers, describe a road, $U_i, V_i, C_i$. There might be multiple edges between $u$ and $v$.\u003c/p\u003e\u003cp\u003eIt is guaranteed that $N \\le 100000, M \\le 200000, K \\le 10$,\u003cbr\u003e$0 \\le C_i \\le 1e9$. There is at least one path between City $1$ and City $N$.\u003c/p\u003e\u003ch3\u003eOutput\u003c/h3\u003e\u003cp\u003eFor each test case, print the minimum distance.\u003c/p\u003e"}},{"title":"Sample 1","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\u003e1\n5 6 1\n1 2 2\n1 3 4\n2 4 3\n3 4 1\n3 5 6\n4 5 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}