问题 23771 --QiQi and Bridges

23771: QiQi and Bridges

时间限制: 3 Sec  内存限制: 128 MB
提交: 3  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

给n个点m条边,边是双向边每条边有固定边权,现在QiQi想从点1开始每条边(双向边经过其中一条就算经过这条边)经历一次再回到出发点,给出一条路径使得路径上最大权值最小。

输入

输入一个n和m表示n个点,m条双向边。接下来输入n行,每行输入4个数a,b,c,d,表示a到b的有向边边权是c,b到a的有向边边权是d。2 <= n <= 1000,1 <= m <= 2000,权值小于1000。

输出

输出一个数q表示路径经过多少个点,接下来输出q个数,表示路径经过的点,起点不用输出。

样例输入

4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4

样例输出

4
4 3 2 1

来源

 

[提交][状态]