说明

时间限制：1 Sec 内存限制：256 MB 输入文件：truck.in 输出文件：truck.out

小明所在的 XM 国中有编号从 $1$ 到 $N$ 的 $N$ 个路口，以及连接这些路口的 $M$ 条道路。路口 $a_i$ 和路口 $b_i$ 之间，由一条长度为 $c_i$ 的道路相连。

XM 国即将举办祭典，期间卡车需要在路口处完成 $90^\circ$ 转弯操作。为此，计划将所有卡车集中到同一个路口。

小明拥有一辆拖车，该拖车每次只能吊起并运输一辆卡车。

拖车初始停放在路口 $L$，而每个路口 $i$ 停放着 $t_i$ 辆卡车。

请你计算：要将所有卡车集中到同一个路口，拖车需要行驶的最短总移动距离。

输入格式

第一行三个整数 $N$、$M$ 和 $L$。

第二行 $N$ 个整数 $t_1,t_2,\cdots,t_N$。

接下来 $M$ 行，第 $i$ 行三个整数 $a_i,b_i,c_i$。

输出格式

输出将所有卡车集中到同一路口时，拖车需要行驶的最短总移动距离。

若所有卡车原本就已经集中在同一个路口，则输出 $0$。

样例

样例 1

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

12

样例说明：

以下方案可实现最短距离运输：

1.  从路口 $1$ 行驶至路口 $2$，吊起 $1$ 辆卡车；

2.  从路口 $2$ 返回路口 $1$，卸下卡车；

3.  从路口 $1$ 行驶至路口 $3$，吊起 $1$ 辆卡车；

4.  从路口 $3$ 返回路口 $1$，卸下卡车；

5.  从路口 $1$ 行驶至路口 $4$，吊起 $1$ 辆卡车；

6.  从路口 $4$ 返回路口 $1$，卸下卡车。

总行驶距离：$(1+1)+(2+2)+(3+3)=12$。

样例 2

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

19

样例说明：

以下方案可实现最短距离运输：

$1→2 → 2→4 → 4→2 → 2→4 → 4→3 → 3→4 → 4→5 → 5→4 → 4→5 → 5→4$。

样例 3

7 9 1
1 1 1 1 1 1 1
1 7 3
2 3 3
2 5 4
3 4 5
3 5 1
3 7 6
4 6 2
5 6 7
6 7 9

53

样例说明：

以下方案可实现最短距离运输：

$1→7 → 7→3 → 3→2 → 2→3 → 3→4 → 4→3 → 3→5 → 5→3 → 3→4 → 4→6 → 6→4 → 4→3 → 3→7 → 7→3$。

数据范围

对于 40% 的数据，满足 $N \le 10$，$M \le 20$。

对于 100% 的数据，满足 $2\leq N\leq 2000$，$N-1\leq M\leq 2000$，$0\leq t_i\leq 2000$，$1\leq\sum t_i$，$1\leq L,\ a_i,\ b_i\leq N$，$1\leq c_i\leq 10^6$。由路口和道路构成的图是连通图。