P9650 [SNCPC2019] Escape Plan

宝宝被困在了 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$。