3073. 道路排序

单点时限: 2.0 sec

内存限制: 256 MB

平面上有 $N$ 个结点,结点编号为 $1,2,3,\cdots ,N$。

这 $N$ 个结点中有 $M$ 条道路。每条道路采用如下格式表示:$(i,j,a_{ij}),i\neq j$,即:结点 $i$ 与结点 $j$ 之间有一条道路,道路长为 $a_{ij}$。

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

图中,结点 $1$ 和结点 $7$ 之间有一条道路,道路长为 $30$,结点 $1$ 与结点 $2$ 之间有一条道路,道路长为 $28$。

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

输入格式

第 1 行:整数 $T$ ($1 \le T \le 10$) 为问题数。

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

第 1 行:输入两个正整数 $N$,$M$,($2 \le N \le 200,1 \le M \le \frac{N\times (N-1)}{2}$),$N$ 表示结点的个数,$M$ 表示道路数。

接下来 $M$ 行,每行输入三个正整数 $i,j,a_{ij}$,($1\le i\le N,1\le j\le N,i\neq j, 1≤a_{ij}≤500$),表示结点 $i$ 到结点 $j$ 之间有一条道路,道路长度为 $a_{ij}$,数之间由一个空格分隔。

输出格式

对于每个问题,输出一行问题的编号(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)

346 人解决,370 人已尝试。

457 份提交通过,共有 947 份提交。

1.4 EMB 奖励。

创建: 5 年,1 月前.

修改: 1 年,10 月前.

最后提交: 2 周,1 天前.

来源: N/A

题目标签