### 题目描述
在一个国家中有许多城市，它们两两之间被双向的公路连接。公路检查员想要穿过几条指定的公路，他需要借助其他的公路来到达指定的公路，他穿过每条公路的时间是固定的，而且他可以任意选择起点和终点，请问他最少用多少时间穿过所有指定的公路？

### 输入格式
**输入有多组数据。** 每组数据第一行有三个数据：城市的数量 $V(1 \le V \le 1000)$ ，指定公路的数量 $E(0 \le E \le V * (V-1)/2)$ ，穿过一条公路需要的时间 $T(1 \le T \le 10)$，接着的每一行都包含两个整数 $a$ 和 $b(1 \le a,b \le V,a \ne b)$，表示指定公路连接的两个城市，输入以三个 $0$ 结尾。

### 输出格式
对于一组数据，输出序号和最少需要的时间。