{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e国家里有$N$个城市,从$u$到$v(1\\le u, v\\le n)$有$M$条单向道路。每条道路都有长度$c_i$。Haze是一个住在$1$城市的魔法少女,她可以选择不超过$K$条道路,并使它们的长度变为$0$。现在她想去$N$城市,请帮她计算最短距离。\u003c/p\u003e\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cp\u003e第一行有一个整数$T(1 \\le T\\le 5)$,然后是$T$个测试用例。\u003c/p\u003e\n\u003cp\u003e对于每个测试用例,第一行有三个整数$N, M$和$K$。\u003c/p\u003e\n\u003cp\u003e接下来的$M$行,每行有三个整数,描述一条道路,$U_i, V_i, C_i$。在$u$和$v$之间可能有多条边。\u003c/p\u003e\n\u003cp\u003e保证$N \\le 100000, M \\le 200000, K \\le 10$,\u003cbr\u003e$0 \\le C_i \\le 1e9$。城市$1$和$N$之间至少有一条路径。\u003c/p\u003e\n\u003ch3\u003e输出\u003c/h3\u003e\n\u003cp\u003e对于每个测试用例,打印最短距离。\u003c/p\u003e"}},{"title":"示例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"}}]}