题目描述

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

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

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

输入格式

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

第二行第一个数据是正整数 $m$，紧接着有 $m$ 个整数 $\verb|vd|_i$，每个整数表示一个目的城市编号。

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

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

输出格式

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

输入输出样例

7 1
8 2 3 4 5 6 7 8 9
1 2 100
1 3 300
1 4 400
2 3 100
3 4 100
2 5 400
3 5 300
3 6 300
4 6 100
5 6 100
5 7 100
6 7 300
8 9 100
2 1 200
3 2 200
3 1 200
4 3 300
7 5 200
6 4 300
6 3 400
3 2 400
9 8 200

100
200
300
500
400
600
NONE
NONE

说明/提示

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