题目描述

$n$ 座城市，编号依次为 $1,2,3,...,n$，其中有些城市之间开通了高铁专列，高铁专列只在两座城市间往返，中途不停靠任何站点。现在给出所有城市间各高铁专列的票价，求从城市 $\verb|vs|$ 出发到城市 $\verb|vd|$ 乘坐高铁专列（可以途径其他城市换乘）的最小费用以及具体的出行方案。

注意：如果城市 $a、b$ 间开通了某列高铁专列，那么该列高铁专列可以 $a$ 出发到达 $b$ ，也可以从 $b$ 出发到达 $a$，并且不管从哪个城市出发，票价都相同。已知有些城市间可能开通了多列高铁专列。

假设不考虑换乘等车耗费的时间，只考虑如何设计出行方案花费最小。

输入格式

第一行是三个正整数 $n,\verb|vs|,\verb|vd|$，分别表示城市数量、出发城市编号和目的城市编号。

后面有若干行，每行三个整数 $\verb|v1|_i,\verb|v2|_i,w_i$，表示一列往返 $\verb|v1|_i$ 和 $\verb|v2|_i$ 的城市间的高铁专列的票价为 $w_i$。

所有数据间用一个空格隔开。

输出格式

第一行输出从城市 $\verb|vs|$ 出发到城市 $\verb|vd|$ 乘坐高铁专列（可以途径其他城市换乘）的最小费用；如果从城市 $\verb|vs|$ 出发乘坐高铁专列无法到达城市 $\verb|vd|$ ，则输出 NONE。

如果存在高铁专列出行最小费用方案，接下来有若干行，每行是一种出行方案，例如：1->2->5->4 就描述了一个从城市 $1$ 途经城市 $2、5$ 到达城市 $4$ 的高铁专列出行方案。

因为可能存在多个方案都满足最小费用，此时优先输出途经城市数少的方案。对于途经城市数相同的方案，优先输出方案依次经过城市编号组成的序列字典序小的方案（具体可以分析输出样例）。

输出时不用考虑两座城市间具体乘坐哪一列高铁专列（如果乘坐两座城市间的多列高铁都能满足最小费用）。

输入输出样例

7 1 7
1 2 300
1 3 100
7 1 1200
1 4 200
2 3 200
3 4 100
2 5 200
2 1 600
2 7 900
3 5 400
4 5 300
5 2 400
4 6 200
1 7 1000
5 7 500
6 7 600
7 2 700

1000
1->7
1->2->7
1->2->5->7
1->3->2->7
1->3->5->7
1->4->5->7
1->4->6->7
1->3->2->5->7
1->3->4->5->7
1->3->4->6->7

说明/提示

👀️ 对于$100\%$ 的数据，$10 \leq n \leq 100,1 \leq \verb|vs|,\verb|vd|,\verb|v1|_i,\verb|v2|_i \leq n,\verb|vs| \neq \verb|vd|,\verb|v1|_i \neq \verb|v2|_i,1\leq w_i \leq 1000$。