题目描述

小 Y 做作业的时候突然想造一条龙舟。龙舟需要龙头、龙身、龙尾三个部分，为了集齐这三个部分，小 Y 想知道，他最少要走多长的路。

镇上有 \(n\) 个房子。小 Y 的家编号为 \(s\) ，其余的每座房子都有三种部件中的一个。有 \(m\) 条路**连通**了这些房子，每条路有一个长度 \(w\) 。小 Y 每走到一个地方就可以获得那里的部件。（他自己家里一个也没有）求他至少走多远才能拿到龙头、龙身、龙尾三种部件至少各一个。

输入格式

第一行一个整数 \(T\) 表示测试点编号。

接下来一行三个整数 \(n,m,s\) 。

接下来一行 \(n\) 个数，第 \(i\) 个整数 \(a_i\) 在 0 到 3 之间，表示这座房子的部件种类。当且仅当 \(i=s\) 时， \(a_i=0\) ，表示家里没有部件。

接下来 \(m\) 行，每行三个整数 \(u,v,w\) 分别表示这条路连接的两座房子和路的长度。

输出格式

一行一个整数表示答案。

保证三种部件均存在。

样例

样例输入 1

0
5 5 1
0 1 2 3 2
1 2 1
2 3 2
5 3 2
3 4 1
1 3 3

样例输出 1

4

提示说明

原图为简单无向图。

数据范围及限制如下。

数据点编号	\(n\)	\(m\)	\(w\)	特殊性质
\(1-3\)	\(\le 100\)	\(\le 500\)	\(\le 10^4\)	无
\(4-6\)	\(\le 10^5\)	\(\le 3\times 10^5\)	\(\le 10^9\)	A
\(7-10\)	\(\le 10^5\)	\(\le 3\times 10^5\)	\(\le 10^9\)	无

特殊性质 A ：只有1个节点有龙头，只有1个节点有龙尾。

对于 100% 的数据，保证：

\(1\le n\le 10^5\)

\(n-1\le m\le min(\frac{n\times (n-1)}{2},3\times 10^5)\)

\(1\le u,v\le n\)

\(1\le w\le 10^9\)