{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"n个点m条边的带权有向图。求从点s到点t的最短合法路径长度。合法路径是指,该路径上的每条边都不在s到t的任意一条最短路上。"}},{"title":"Input","value":{"format":"HTML","content":"包含多组数据。\n\u003cp\u003e\n\u003cp\u003e第一行两个整数n和m (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 500, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e4\u003c/sup\u003e\u003c/span\u003e),节点编号从0到n-1。\n\u003cp\u003e第二行两个整数s和t(0≤s,t≤n-1),表示起点和终点。\n\u003cp\u003e接下来m行,每行3个整数u,v,p(0≤u,v≤n-1,1≤p≤10\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e),表示点u到点v有一条权值为p的有向边。\u003c/p\u003e\n"}},{"title":"Output","value":{"format":"HTML","content":"每一组数据输出一行,每行只有一个整数。有解输出s到t的最短合法路径长度,无解输出-1。"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e\n7 9\u003cbr\u003e0 6\u003cbr\u003e0 1 1\u003cbr\u003e0 2 1\u003cbr\u003e0 3 2\u003cbr\u003e0 4 3\u003cbr\u003e1 5 2\u003cbr\u003e2 6 4\u003cbr\u003e3 6 2\u003cbr\u003e4 6 4\u003cbr\u003e5 6 1\u003cbr\u003e4 6\u003cbr\u003e0 2\u003cbr\u003e0 1 1\u003cbr\u003e1 2 1\u003cbr\u003e1 3 1\u003cbr\u003e3 2 1\u003cbr\u003e2 0 3\u003cbr\u003e3 0 2\u003cbr\u003e6 8\u003cbr\u003e0 1\u003cbr\u003e0 1 1\u003cbr\u003e0 2 2\u003cbr\u003e0 3 3\u003cbr\u003e2 5 3\u003cbr\u003e3 4 2\u003cbr\u003e4 1 1\u003cbr\u003e5 1 1\u003cbr\u003e3 0 1\u003cbr\u003e0 0\u003cbr\u003e\n\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e5\u003cbr\u003e-1\u003cbr\u003e6\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e "}}]}