题目描述

小 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

提示说明

原图为简单无向图。

数据范围及限制如下。

特殊性质 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$