题目描述

有 $n$ 个城市，编号为 $1 \sim n$，城市之间有 $m$ 条双向道路，每条道路有一个正整数长度。请你求出从起点 $s$ 到终点 $t$ 的最短距离，以及最短路径上经过的城市编号。

如果从 $s$ 到 $t$ 存在多条长度相同的最短路径，请输出字典序最小的那条路径；若不存在从 $s$ 到 $t$ 的路径，请输出 can't arrive。

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

输入格式

第一行包含四个正整数 $n, m, s, t$，分别表示城市的数量、道路的数量、起点编号、终点编号。

接下来 $m$ 行，每行三个正整数 $x, y, len$，表示一条连接城市 $x$ 和城市 $y$ 的双向道路，道路长度为 $len$。

输出格式

如果存在从起点 $s$ 到终点 $t$ 的路径：

• 第一行输出一个整数，表示 $s$ 到 $t$ 的最短距离。
• 第二行输出若干个用空格分隔的整数，表示最短路径上依次经过的城市编号。若有多条最短路径，输出字典序最小的那条。

如果不存在从起点 $s$ 到终点 $t$ 的路径，仅输出一行字符串 can't arrive。

样例

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

2
1 2 3

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

2
1 2 6 4

样例解释

• 样例 1：$1 \to 3$ 直接距离为 $3$，但 $1 \to 2 \to 3$ 距离为 $2$，后者更短且字典序为 1 2 3。
• 样例 2：$1 \to 2 \to 6 \to 4$ 距离为 $2$，字典序比另一条路径 $1 \to 5 \to 3 \to 4$ 更小。

数据范围

• $1 \leq n < 1000$
• $1 \leq m < 10000$
• $1 \leq s, t \leq n$
• $1 \leq x, y \leq n$
• $1 \leq len \leq 50000$