算法分析与设计习题 (参考)

N. 你是ACM吗?

单点时限: 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 行,每行输出一个值,对应于相应的用列的最少耗费。

样例

Input
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
Output
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);