【基础】最短距离和路径问题
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
有个城市（编号为1~），条道路，每条道路有个长度，请找到从起点到终点的最短距离和经过的城市名。
输入格式
第一行输入四个数，分别为。
接下来行，每行三个数，分别为两个城市名和距离。
输出格式
每组输出占两行。
第一行输出起点到终点的最短距离。
第二行输出最短路径上经过的城市名，如果有多条最短路径，输出字典序最小的那条 。若不存在从起点到终点的路径，则输出“can't arrive”。
请注意：本题两个相同的城市之间可能存在多条路径。
样例
3 3 1 3
1 3 3
1 2 1
2 3 1
2
1 2 3
4 3 1 4
1 2 3
1 2 1
2 3 1
can't arrive