程序设计能力实训

1039. 道路排序

单点时限: 2.0 sec

内存限制: 256 MB

平面上有 个结点,结点编号为

个结点中有 条道路。每条道路采用如下格式表示:,即:结点 与结点 之间有一条道路,道路长为

注意:任意两个结点之间最多只有一条道路。

图中,结点 和结点 之间有一条道路,道路长为 ,结点 与结点 之间有一条道路,道路长为

请将这 条道路按照长度递减排序;如果道路长度相等,则按照道路的第一个结点编号 递增排序;如果第一个结点编号 相同,则按照第二个结点编号 递增排序。

输入格式

第 1 行:整数 () 为问题数。

对于每个问题,按如下格式输入:

第 1 行:输入两个正整数 ,(), 表示结点的个数, 表示道路数。

接下来 行,每行输入三个正整数 ,(),表示结点 到结点 之间有一条道路,道路长度为 ,数之间由一个空格分隔。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等)。

接下输出排序后的 M 条道路。每行输出一条道路。具体格式见 SampleOutput。

样例

Input
3
10 12
1 7 30
1 2 28
2 4 20
2 5 10
2 3 10
3 10 10
7 5 20
5 10 70
8 5 20
8 6 40
7 6 35
6 9 10
2 1
1 2 30
4 6
1 3 30
2 3 19
1 2 30
1 4 19
2 4 50
4 3 30
Output
case #0:
(5,10,70)
(8,6,40)
(7,6,35)
(1,7,30)
(1,2,28)
(2,4,20)
(7,5,20)
(8,5,20)
(2,3,10)
(2,5,10)
(3,10,10)
(6,9,10)
case #1:
(1,2,30)
case #2:
(2,4,50)
(1,2,30)
(1,3,30)
(4,3,30)
(1,4,19)
(2,3,19)
不限期开放

题目列表