上学路线

可可和卡卡家住HF市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。

可可：“很可能我们在上学的路途上浪费了大量的时间，让我们写一个程序来计算上学需要的最少时间吧！”

HF市一共设有N个公交车站，不妨将它们编号为 1…N的自然数，并认为可可和卡卡家住在 1 号汽车站附近，而他们学校在N号汽车站。市内有M条直达汽车路线，执行第i条路线的公交车往返于站点pi 和qi 之间，从起点到终点需要花费的时间为t i。 (1<=i<=M, 1<=p i,q i<=N)

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

[ 任务 ]

编写一个程序：

•  从输入文件中读取HF市公交路线的信息；

•  计算出实际上可可和卡卡上学需要花费的最少时间；

•  帮助可可设计一个方案，删除输入信息中的一些公交路线，使得删除后从家到学校需要的最少时间变大，而被删除路线的c i和最小；

•  向输出文件输出答案。

[ 输入格式 ]

输入文件中第一行有两个正整数N和M，分别表示HF市公交车站和公交汽车路线的个数。以下M行，每行（第i行，总第 (i+1) 行）用四个正整数描述第i条路线：p i,q i,t i,c i；具体含义见上文描述。

[ 输出格式 ]

输出文件最多有两行。

第一行中仅有一个整数，表示从可可和卡卡家到学校需要的最短时间。

第二行描述你为可可制定的方案，首先有两个整数K和C，表示总共需要删除K条路线，它们的c i之和为C最小；

接着有K行，每行1个 1…N的正整数：d1 ,d2 , …,d K，表示需要删除的路线编号，即输入文件中顺数的编号。如果有多解，输出任意一个。

[ 输入样例 ]

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

[ 输出样例 ]

2
2 5

1

6

[ 数据约束 ]

2<=N<=500, 1<=M<=124 750, 1<=t i,c i<=10 000（评测插件有些问题，如果评测结果有误，请下载数据手动评测——Mike）

HF市的公交网络十分发达，你可以认为任意两个车站间都可以通过直达或转车互相到达，当然如果在你提供的删除方案中，家和学校无法互相到达，那么则认为上学需要的最短为正无穷大：这显然是一个合法的方案。