题目描述

$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|v|_p$ 和 $\verb|v|_q$ 间的所有高铁，按照输入的顺序编号依次为 $1,2,3...$。

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

输出格式

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

如果存在高铁专列出行最小费用方案，接下来有若干行，每行一种出行方案，例如：1[2,200]->2[4,300]->5[2,400]->4 就描述了一个从城市 $1$ 途经城市 $2$（乘坐 $1、2$ 两座城市间编号为 $2$ 的高铁专列，车票费用为 $200$）、$5$ （乘坐 $2、5$ 两座城市间编号为 $4$ 的高铁专列，车票费用为 $300$）到达城市 $4$ （乘坐 $4、5$ 两座城市间编号为 $2$ 的高铁专列，车票费用为 $400$）的高铁专列出行方案。

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

输入输出样例

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

1000
1[1,1000]->7
1[2,1000]->7
1[1,300]->2[2,700]->7
1[1,300]->2[3,700]->7
1[3,300]->2[2,700]->7
1[3,300]->2[3,700]->7
1[1,100]->3[1,200]->2[2,700]->7
1[1,100]->3[1,200]->2[3,700]->7
1[1,200]->4[1,200]->6[1,600]->7
1[1,200]->4[2,200]->6[1,600]->7
1[1,100]->3[1,100]->4[1,200]->6[1,600]->7
1[1,100]->3[1,100]->4[2,200]->6[1,600]->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$。两座城市间开通的高铁专列数量不超过 $100$。