No testdata at current.

Background

《Minecraft》是一款沙盒类电子游戏，开创者为马库斯·阿列克谢·泊松（Notch）。游戏由Mojang Studios维护，现隶属于微软Xbox游戏工作室。 生电，即生存电路。指玩家在生存模式下建造的以大量生产生存资源为目的的基于游戏特性或红石电路运行的机器。 一般情况下，一个生电存档发展到后期往往会面临着生产机器分部过于分散的情况（因为有些机器需要建造在特殊区块当中），此时，修建一个快捷且完备的物资运输系统就十分必要了。

Description

玩家inclusing的生电存档玩了已经一年有余了，已经发展出了相对完善的工业系统了，美中不足的是这个存档的种子并不是很好，导致集中管理机器的难度大幅增加。 于是inclusing在主世界建造了一个铁路运输系统（不同站点之间连接的铁路都是双向的），并给每个站点编号，但是他却因为规划物资在站点之间往返的最短路径而苦恼。 请你编写一个程序，帮助他求出从给定的起始站点到目的地的最短路径和最短距离。

Format

输入为一个无向图，以及起点和终点编号。 输出为最短路径和最短距离。

Input

第一行分别输入一个大于 2 的正整数 n 和一个大于 2 的正整数 m ，分别代表图的顶点数和边数； 接下来 n 行分别输入 i 和 j 和 l ，代表站点 i 和站点 j 之间存在长度为 l 的连接的铁路； 第 n+2 行分别输入起始站点编号 s 和目的地站点编号e。

Output

第一行输出最短路径的总距离 ans； 依次输出最短路径，每输出一步换行。

Samples

5 8
1 2 2
1 3 12
1 4 10
2 3 8
2 5 12
3 4 6
3 5 3
4 5 7
1 5

13
1 -> 2
2 -> 3
3 -> 5

Limitation

0 < l <= 32767 , 2 < m,n < 50 , ; 1s , 1024KiB.