43 人解决，152 人已尝试。
73 份提交通过，共有 480 份提交。
6.3 EMB 奖励。
单点时限: 15.0 sec
内存限制: 256 MB
随着中国经济的腾飞，中国的物流产业迎来了发展的春天。特别是在上海这样一个拥有广阔国内腹地的国际化大都市，物流业以空前的速度膨胀。
当然是大蛋糕就会吸引许多馋嘴猫，馋嘴猫多了就会有残酷的竞争。当大量资金流入物流产业时，KOP 集团为了稳坐在国内物流业的第一把交椅，决定对现行的运输方案进行改良，以减少自己的成本同时使其它竞争者知难而退。
作为世界 100 强的 KOP 集团当然知道要找到最优运输方案，肯定得靠数学和算法很好的软件工程师，于是他们理所当然地找到华东师范大学软件学院。决定通过赞助一场程序比赛来找出最优秀的工程师 ( ACM : Ace Coding Man )。
比赛只有一道题目，是运输线路的简单抽象，题意如下：
SH 市有 N 个运输中转点 (简单标示为 1,2,3,....,N)，中转点之间可能有一条运输线路，这条线路有一个特殊的地方就是从 A 到 B 点需要耗费 c1 个单位的查克拉 (SH 市的货币单位)，但从 B 到 A 可能需要 c2 个查克拉。当然 c1 不一定等于 c2，也能从 A 到 B 之后就不能从 B 返回 A 了。你可以理解为这些线路是“单向”的。线路总共有 M 条。每天有 N-1 辆车从 KOP 集团总部 (这里假设就是标号为 1 的中转点)，出发，分别发往 N-1 个剩下的中转点，然后当天再从所到达的中转点返回。你的任务就是要求出一天的最小耗费。
第一行为 C ，表示有 C 个测试用列。接下来分别为 C 个测试用列。
每个测试用例的格式如下：
第一行为两个整数，N，M，分别表示有 N 个中转点和 M 条道路。( 1=< N, M <=1000000 .);
紧接着的 M 行每行有三个值 A B c； 分别表示从中转点 A 到中转点 B 需要耗费 c 个单位的查克拉。 ( 0<= c <= 1000000000 ).
你的输出应该包括 C 行，每行输出一个值，对应于相应的用列的最少耗费。
2 2 2 1 2 13 2 1 33 4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50
46
210
注意：
1、输入数据量很大，大于4MB。建议用C 语言的形式读入以避免超时。
读入整数为 : int n; scanf("%d", &n); (等价于 cin>>n ).
2、数据处理可能会超过C++的int表示范围，建议换成 __int64 数据类型（VC6.0编译条件下)。如果你选用G++，则为 long long.
相应的输出方法为： __int64 i64; printf("%I64d", i64);
43 人解决，152 人已尝试。
73 份提交通过，共有 480 份提交。
6.3 EMB 奖励。