Problem H: 城市导航B
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：17
Solved：12
Description
寒假到了，小明想到小红家去玩，小明和小红住在不同的城市，并且小明之前从来没有去过小红家，这是小明第一次上门。怎么去呢？小明便想起了百度地图。百度地图一下子找到了从小明家到小红家的最短行车方案。爱思考的小明想知道百度地图是如何计算出最短行车方案的。下面是城市的一张样图。
Input
第一行n和m（n<=100，m<=500），n表示城市数，m表示各城市之间的路程。
第二行x和y，x表示起点城市编号，y表示目的城市编号。
从第3行起的连续m行，每行三个数据a，b，c，分别表示城市a到城市b的距离为c。
Output
第一行输出起点x城市到目的y城市的最短路程。如果无法到达，输出-1。
如果能到达，则第二行输出从起点到目的地经过的所有城市编号。
Sample Input Copy
5 8
1 5
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3
Sample Output Copy
9
1 2 5HINT
样例输入说明：
5
8 （5-代表城市数，8-代表各城市间的路程）
1
5 （1-表示起点城市，5-表示目的城市）
1
2 2 （城市1和城市2的路程为2，下列数据含义相同））
1
5 10
2
3 3
2
5 7
3
1 4
3
4 4
4
5 5
5 3 3
样例输出说明：
9 （从1号城市到5号城市的最短路程为9）
1
2 5 （最短路程经过的城市号为1 2 5）