题目描述

魔法学院有$\red{n(1≤}$$\red{n≤}$$\red{50)}$个街区,某些街区有公共汽车线路相连,如图所示,

街 区$\red{1}$和街区$\red{2}$有一条公共汽车线路相连.且由街区$\red{1}$至街区$\red{2}$的时间为$\red{34}$分钟,由街区$\red{1}$ 至街区$\red{5}$最快走法是$\red{1-3-5,}$总时间为$\red{44}$分钟。 魔法学院为了改善交通状况,决定增加$\red{m(1≤}$$\red{m≤}$$\red{10)}$条公 共汽车线路,若在某两街区$\red{a}$和$\red{b}$之间加开线路,前提是$\red{a}$和$\red{b}$ 之间必须已有线路,则从$\red{a}$到$\red{b}$的通行时间缩小为原来一半， 例如,若在$\red{1}$和$\red{2}$之间加开一条线路,时间变为$\red{17}$分钟，若加开 两条线路,时间变为$\red{8.5}$分钟，依次类推,所有的线路都是环线， 即如果由$\red{1}$至$\red{2}$时间变为$\red{17}$分钟，则由$\red{2}$至$\red{1}$的时间也变为$\red{17}$ 分钟。求加开某些线路,能使由$\red{1}$至$\red{n}$的时间最少。例如,$\red{m=2,}$则加开$\red{1-3,3-5}$的线路,总. 时间可以减少为$\red{22}$分钟。求加开哪些线路,可使街区$\red{1}$到$\red{n}$的时间最短,并输出增加的线路。

输入格式

第一行为街区数$\red{n}$和增加公共汽车线路数$\red{m}$。 随后的每一行三个整数$\red{x,y,d,}$表示$\red{x}$街区到$\red{y}$街区的通行时间$\red{d}$

输出格式

第一行为从街区$\red{1}$到街区$\red{n}$的最短时间。 随后$\red{m}$行表示增加的线路.线路需按前后顺序依次输出。

样例

输入样例

5 2
1 2 34
1 3 24
2 3 10
2 4 12
3 4 16
3 5 20
4 5 30

输出样例

22
1 3
3 5