题目描述

BaoBao, one of the most famous monster hunters, wakes up in the middle of Heltion City dominated by monsters. Having troubles remembering what has happened, BaoBao decides to escape from this horrible city as soon as possible. Despite arming no weapon, he luckily puts his hand on a map in his right pocket, which contains valuable information that can possibly help him find a way out.

According to the map, Heltion City is composed of $n$ spots connected by $m$ undirected paths. Starting from spot $1$, BaoBao must head towards any of the $k$ exits of the city to escape, where the $i$-th of them is located at spot $e_i$.

However, it's not an easy task for BaoBao to escape since monsters are everywhere in the city! For all $1 \le i \le n$, $d_i$ monsters are wandering near the $i$-th spot, so right after BaoBao arrives at that spot, at most $d_i$ paths connecting the spot will be blocked by monsters and are unable for BaoBao to pass. When BaoBao leaves the $i$-th spot, the monsters will go back to their nests and the blocked paths are clear. Of course, if BaoBao comes back to the spot, at most $d_i$ paths will be again blocked by the monsters. The paths blocked each time may differ.

As BaoBao doesn't know which paths will be blocked, please help him calculate the shortest time he can escape from the city in the worst case.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ (about $100$), indicating the number of test cases. For each test case:

The first line contains three integers $n$, $m$ and $k$ ($1 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le k \le n$), indicating the number of spots, the number of undirected paths and the number of exits of the city.

The second line contains $k$ distinct integers $e_1, e_2, \dots, e_k$ ($1 \le e_i \le n$), indicating $k$ exits of Heltion City.

The third line contains $n$ integers $d_1, d_2, \dots, d_n$ ($0 \le d_i \le m$), where $d_i$ indicates the number of monsters at the $i$-th spot.

For the following $m$ lines, the $i$-th line contains three integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i,y_i \le n$, $x_i \neq y_i$, $1 \le w_i \le 10^4$), indicating an undirected edge of length $w_i$ connecting spot $x_i$ and $y_i$.

It's guaranteed that the total sum of $n$ will not exceed $10^6$ and the total sum of $m$ will not exceed $3 \times 10^6$.

输出格式

For each case output one line containing one integer. If BaoBao can get to some exit in the worst case, output the shortest possible time cost; Otherwise if BaoBao cannot get to any exit in the worst case, output -1 instead.

题目大意

题目描述

宝宝被困在了 Heltion 城中。

城市可以看做由 $n$ 个点与 $m$ 条边组成的有权无向图，最开始宝宝在 $1$ 号节点。城市中存在 $k$ 个出口，第 $i$ 个出口位置在 $e_i$ 号点 ，而宝宝需要以最快的速度到达这些出口中的任意一个以逃离 Heltion 城。

不巧的是，城市中有怪物游荡，对于点 $i$，有 $d_i$ 只怪物驻守在此。当宝宝到达点 $i$ 时，怪物会随机封锁至多 $d_i$ 条与之相邻的道路，宝宝不能通过这些被封锁的道路。而当宝宝离开后，点 $i$ 的怪物会回窝，这时被封锁的道路会解开。

请帮帮宝宝，求出最坏情况下，他逃出 Heltion 城需要多久。

输入格式

第一行为一个正整数 $T$，表示有 $T$ 组测试数据。

对于每组数据，第一行包括三个正整数 $n$，$m$，$k$，分别表示城市的点数，边数和城市中出口的数量。

第二行有 $k$ 个正整数 $e_1, e_2,\dots , e_k$，表示第 $i$ 个出口在 $e_i$ 号节点。

第三行有 $n$ 个正整数 $d_1, d_2,\dots , d_n$，表示第 $i$ 个节点上有 $d_i$ 只怪物。

接下来的 $m$ 行，一行三个正整数 $x_i$，$y_i$，$w_i$，表示第 $i$ 条双向边所连接的两点与边权。

输出格式

共 $T$ 行，每行一个整数。第 $i$ 行的整数表示第 $i$ 组数据的答案。

对于每组数据，若宝宝不能到达任何一个出口，请输出 -1。否则，输出宝宝到达任意一个出口所需要的最少时间。

数据范围

对于 $100\%$ 的数据，$1\le n \le 10^5$，$\sum n \le 10^6$，$1\le m \le 10^6$，$\sum m \le 3\times 10^6$，$1\le k \le n$，$1\le e_i \le n$，$0\le d_i \le m$，$1\le x_i,y_i \le n$，$1\le w_i \le 10^4$。数据保证 $x_i \neq y_i$。

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

4
-1