{"trustable":false,"sections":[{"title":"Description","value":{"format":"MD","content":"队里没有小姐姐,所以学长们都快抢不到饭了。2333\n~~董洪益为了其他学长有饭吃,毅然选择女装.所以大部分学长吃上了饭,而学弟们也有小姐姐了2333~~\nN-1位小姐姐来自除长春之外N-1座不同的城市,加上长春,一共N座城市。一共有M条**单向**道路连接着这N座城市。询问每个小姐姐从家中来到长春,再从长春回到各自家中的最短路径和是多少。"}},{"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长春的编号是1,其余的城市编号为2..N-1。"}},{"title":"Output","value":{"format":"MD","content":"对于每个案例,打印一行,表示小姐姐们从家中来到长春,再从长春回到各自家中的最短路径和是多少。(你可以假设答案不会是无限大,且答案在long long范围内)"}},{"title":"Sample Input","value":{"format":"MD","content":"2\n2 2\n1 2 13\n2 1 33\n4 6\n1 2 10\n2 1 60\n1 3 20\n3 4 10\n2 4 5\n4 1 50"}},{"title":"Sample Output","value":{"format":"MD","content":"46\n210"}}]}