C1447 [AHOI2006]上学路线

可可和卡卡家住合肥市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。可可：“很可能我们在上学的路途上浪费了大量的时间，让我们写一个程序来计算上学需要的最少时间吧！” 合肥市一共设有 $N$ 个公交车站，不妨将它们编号为 $1…N$ 的自然数，并认为可可和卡卡家住在 $1$ 号汽车站附近，而他们学校在 $N$ 号汽车站。市内有 $M$ 条直达汽车路线，执行第 $i$ 条路线的公交车往返于站点 $p_i$ 和 $q_i$ 之间，从起点到终点需要花费的时间为 $t_i$。$(1 \le i \le M, 1 \le p_i, q_i \le N)$

两个人坐在电脑前，根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线 $i$ 事实上都有一个代价 $c_i$：删去路线的 $c_i$ 越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线 $c_i$ 之和最小。

[任务]

编写一个程序：

• 从输入中读取合肥市公交路线的信息；
• 计算出实际上可可和卡卡上学需要花费的最少时间；
• 帮助可可设计一个方案，删除输入信息中的一些公交路线，使得删除后从家到学校需要的最少时间变大，而被删除路线的 $c_i$ 和最小；输出答案。

样例输入 1

6 7
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4

样例输出 1

2
5