{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"30世纪,X同学领悟了通天大道,开始在各个星球之间穿梭。但因为每次穿梭需要消耗巨大的能量,X同学只好暂时放弃了宇宙遨游的梦想。10年后,他发现每个星球之间的穿梭通道其实隐含着巨大的能量可供飞行,由于X同学天赋异禀,顿悟了吸星大法,他很快踏上了他的宇宙之旅。\n\nX同学从地球(1号星球)出发,准备前往遥远的n号星球。因为有强大的力量束缚X同学的能力,X同学只能见到n个星球(1号到n号),且只能在他能力范围内的m个穿梭通道内通行,并用他顿悟的吸星大法吸取其中的全部或部分能量。两个星球之间有且只有一个穿梭通道。\n\n由于穿梭通道的能量能给X同学带来难以言喻的爽快感,X同学希望自己在能到达n号星球的所有穿梭通道内,每次获得的能量尽可能大。遗憾的是,吸星大法是很容易走火入魔的。如果X同学在路途中的某一个通道内获得过大的能量,且在接下来的路途中,有通道无法提供与之相等的能量,X同学将倍感空虚,进而损伤道基,这显然是不能被X同学所接受的。当然,X同学也不会选择吸收大于前面任何通道吸收的能量,这将可能导致他爆体而亡。换句话说,X同学每次吸收的能量全部相同。所以,X同学必须提前做好功课,确定好每次能获得的最大能量。\n\n"}},{"title":"Input","value":{"format":"MD","content":"题目有多组测试数据。\n\n第一行给一个 **T**。\n\n每一组数据的第一行给两个数n和m,表示X同学能见的n个星球和能通行的m个穿梭通道。\n**(1 \u003c\u003d n \u003c\u003d 1000)**\n\n接下来m行,每行三个数s1,s2,d代表两个星球的编号和它们之间穿梭通道隐含的全部能量。\n**(1 \u003c\u003d s1,s2 \u003c\u003d n , 1 \u003c\u003d d \u003c\u003d 1e6)**\n"}},{"title":"Output","value":{"format":"MD","content":"每组数据先输出一行 Scenario #k,其中 k 是组别编号(从 1 开始)。\n\n下一行输出一个整数,表示X同学每次能获得的最大能量。\n\n最后输出一个空行。\n"}},{"title":"Sample Input","value":{"format":"MD","content":"1\n3 3\n1 2 3\n1 3 4\n2 3 5"}},{"title":"Sample Output","value":{"format":"MD","content":"Scenario #1:\n4"}}]}