{"trustable":false,"sections":[{"title":"Description","value":{"format":"MD","content":"炎龙侠在为他的科幻小说小说中的世界,设计一幅交通图。\n大部分行星之间都建有传送门,但是传送门只能单向通过,而且,因为技术条件的差异,以及设备的老化,每个传送门,传送需要的时间基本都不相同。\n他在小说中设计了一个情节,主角梅川瓦子得到了情报,有外星人要同时对她所在势力的n颗行星发动攻击,她在编号为1的行星上。\n由于超距通讯系统的损坏,她只能派出一架无人机,穿过传送门,前去通知编号2~n的行星。\n有关外星人的资料很多,无人机的存储器无法存下,于是她准备了n-1块硬盘。无人机每次可以携带一块硬盘(根据sy的建议,硬盘应该绑在无人机的腿上),前去通知完一颗行星后,它要回到梅川瓦子身边,再带上新的硬盘,通知下一个行星 \n时间紧迫,梅川瓦子希望你能帮帮她计算一下,无人机前去通知n-1颗行星,再回到它身边,所花费的最短时间的总和"}},{"title":"Input","value":{"format":"MD","content":"输入由T个案例组成。输入的第一行只包含正整数T。\n接下来是N和M,1 \u003c\u003d N,M \u003c\u003d 1000000,表示N个行星和连接N个行星的M个单向传送门。\n然后有M行,每行包括三个值U,V,W,表示从行星U到行星V的传送门,传送需要的时间W。\n"}},{"title":"Output","value":{"format":"MD","content":"对于每个案例,打印一行,表示花费时间总和的最小值。"}},{"title":"Sample Input","value":{"format":"MD","content":"2\n2 2\n1 2 6\n2 1 4\n3 5\n1 2 8\n2 1 16\n1 3 50\n2 3 41\n3 2 47"}},{"title":"Sample Output","value":{"format":"MD","content":"10\n136"}},{"title":"Hints","value":{"format":"MD","content":"注意不要使用万能头文件,不要使用cin和cout"}}]}