{"trustable":false,"sections":[{"title":"问题描述","value":{"format":"HTML","content":"Alice喜欢冒险。现在Alice在一座小岛上,这座岛有许多站,各站之间有些存在着通路,但通路中间有石墙阻挡。Alice可以借助自己随身携带的绳索翻过石墙从而能从一站到达另一站。绳索的长度为L,则所有高度不大于L的石墙Alice都可以翻过。不过绳索是特种工具,太长的绳索重量很大难以携带,Alice希望能尽量短地拿一根绳索并到达目的地。给出Alice的起点和终点,帮助Alice确定最短能完成冒险的绳索长度。"}},{"title":"数据输入","value":{"format":"HTML","content":"多组数据。每组数据有多行,第一行是三个用空格分隔的数字C,S,Q,分别表示有C个小站,S条通路和Q次冒险。接下来有S行,每行有三个数字由空格隔开,分别是c\u003csub\u003e1\u003c/sub\u003e,c\u003csub\u003e2\u003c/sub\u003e,d,表示从c\u003csub\u003e1\u003c/sub\u003e站到c\u003csub\u003e2\u003c/sub\u003e站(c\u003csub\u003e1\u003c/sub\u003e \u0026ne; c\u003csub\u003e2\u003c/sub\u003e)有通路,并且中间有高为d的石墙。接下来Q行,一行中给出两个整数c\u003csub\u003e1\u003c/sub\u003e,c\u003csub\u003e2\u003c/sub\u003e,表示Alice的探险要从c\u003csub\u003e1\u003c/sub\u003e到c\u003csub\u003e2\u003c/sub\u003e(c\u003csub\u003e1\u003c/sub\u003e \u0026ne; c\u003csub\u003e2\u003c/sub\u003e)。\u003cbr\u003e数据最后一行C,S,Q都是0,表示数据输入结束,这一组数据不需要处理\n\u003cul\u003e\n\u003cli\u003eC \u0026le; 100\u003c/li\u003e\n\u003cli\u003eS \u0026le; 1000\u003c/li\u003e\n\u003cli\u003eQ \u0026le; 10000\u003c/li\u003e\n\u003cli\u003e0 \u0026lt; d \u0026le; 100000\u003c/li\u003e\n\u003cli\u003e1 \u0026le; c\u003csub\u003e1\u003c/sub\u003e,c\u003csub\u003e2\u003c/sub\u003e \u0026le; C\u003c/li\u003e\n\u003c/ul\u003e"}},{"title":"数据输出","value":{"format":"HTML","content":"对于每组数据,先在一行中输出编号(从1开始),接下来输出Q行,输出一个数字表示这一个冒险中Alice可带的最短绳子的长度,若Alice选的这两站之间不能连通,则输出\"no path\"。\n\u003cbr\u003e\n每两组数据之间用一个空行隔开。"}},{"title":"样例输入","value":{"format":"HTML","content":"\u003cpre\u003e7 9 3\n1 2 50\n1 3 60\n2 4 120\n2 5 90\n3 6 50\n4 6 80\n4 7 70\n5 7 40\n6 7 140\n1 7\n2 6\n6 2\n7 6 3\n1 2 50\n1 3 60\n2 4 120\n3 6 50\n4 6 80\n5 7 40\n7 5\n1 7\n2 4\n0 0 0\u003c/pre\u003e"}},{"title":"样例输出","value":{"format":"HTML","content":"\u003cpre\u003eCase #1\n80\n60\n60\n\nCase #2\n40\nno path\n80\u003c/pre\u003e"}},{"title":"提示","value":{"format":"HTML","content":"第1组数据如图示:\n\u003cbr\u003e\n\u003cimg width\u003d300 src\u003d\"http://www.malic.xyz/wp-content/uploads/p6h1t.png\"/\u003e\n\u003cbr\u003e\n从1到7若按1,3,6,4,7则只需准备长为80的绳子。2到6按2,1,3,6只需要准备长为60的绳子。"}}]}