[HNOI2006]公路修建问题

题目描述

![](https://cdn.luogu.com.cn/upload/pic/1384.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/pic/1386.png) ![](https://cdn.luogu.com.cn/upload/pic/1387.png) #在实际评测时,将只会有m-1行公路

输出格式


![](https://cdn.luogu.com.cn/upload/pic/1385.png)

输入输出样例

输入样例 #1

4 2 5 
1 2 6 5
1 3 3 1
2 3 9 4
2 4 6 1

输出样例 #1

6 
1 1 
2 1 
4 1