一个简单的最短路问题。

添加标签 最短路。

原题面中输入没有空行，输出只有数据之间有换行。应将样例改为：

in

2
3
1 2
1 3
4
2 2 3
1 1
2 2 4

out

2
1 2

2
1 3