{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e给定一张n个点m条边的带权有向图,每条边的边权只可能是1,2,3中的一种。\u003cbr\u003e 将所有可能的路径按路径长度排序,请输出第k小的路径的长度,注意路径不一定是简单路径,即可以重复走同一个点。\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行包含三个整数n,m,k(1\u0026lt;\u003dn\u0026lt;\u003d40,1\u0026lt;\u003dm\u0026lt;\u003d1000,1\u0026lt;\u003dk\u0026lt;\u003d10^18)。\u003cbr\u003e 接下来m行,每行三个整数u,v,c(1\u0026lt;\u003du,v\u0026lt;\u003dn,u不等于v,1\u0026lt;\u003dc\u0026lt;\u003d3),表示从u出发有一条到v的单向边,边长为c。\u003cbr\u003e 可能有重边。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e包含一行一个正整数,即第k短的路径的长度,如果不存在,输出-1。\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e6 6 11\n1 2 1\n2 3 2\n3 4 2\n4 5 1\n5 3 1\n4 6 3\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e4\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e长度为1的路径有1-\u0026gt;2,5-\u0026gt;3,4-\u0026gt;5。\u003cbr\u003e\u003cbr\u003e 长度为2的路径有2-\u0026gt;3,3-\u0026gt;4,4-\u0026gt;5-\u0026gt;3。\u003cbr\u003e\u003cbr\u003e 长度为3的路径有4-\u0026gt;6,1-\u0026gt;2-\u0026gt;3,3-\u0026gt;4-\u0026gt;5,5-\u0026gt;3-\u0026gt;4。\u003cbr\u003e\u003cbr\u003e 长度为4的路径有5-\u0026gt;3-\u0026gt;4-\u0026gt;5。\u003c/p\u003e\n\u003cbr\u003e \n\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e"}}]}