问题描述

有 $n$ 个城市（编号为 $1$~$n$ ），$m$ 条道路（$n \lt 1000$,$m \lt 10000$)，每条道路有个长度，请找到从起点 s 到终点 t 的最短距离和经过的城市名。

输入格式

第一行输入四个数，分别为 $n$，$m$，$s$，$t$。（$n \lt 1000$, $m \lt 10000$，$1 \le s,t \le n$

接下来 $m$ 行，每行三个数 $x$，$y$，$len$，分别为两个城市名和距离。（$1 \le x,y \le n，1 \le len \le 50000$）

输出格式

每组输出占两行。

第一行输出起点到终点的最短距离。

第二行输出最短路径上经过的城市名，如果有多条最短路径，输出字典序最小的那条。若不存在从起点到终点的路径，则输出“can't arrive”。

请注意：本题两个相同的城市之间可能存在多条路径。

样例

3 3 1 3
1 3 3
1 2 1
2 3 1

2
1 2 3