Graph Evacuation

You are given an undirected connected graph with $N$ nodes and $M$ edges. Each edge has a weight. There are $K$ critical nodes $A_1,A_2,\ldots,A_K$, with corresponding capacities $S_1,S_2,\ldots,S_K$.

The residents in the graph must be evacuated. In particular, you need to construct a sequence $B_1,B_2,\ldots,B_N$ satisfying:

• $1\le B_i\le K$ for every $1\le i\le N$.
• For every $1\le i\le K$, if \(\mathrm{cnt}_i=\sum_{j=1}^{N}[B_j=i]\) (that is, the frequency of $i$ in the sequence), then \(\mathrm{cnt}_i\le S_i\).

The evacuation time of a sequence is defined as \[ T = \max_{1\le i\le N} \operatorname{dist}(i,A_{B_i}), \] where \(\operatorname{dist}(u,v)\) is the shortest path distance between nodes \(u\) and \(v\) in the graph.

Your goal is to minimize \(T\). It is guaranteed that \(\sum_{i=1}^{K}S_i\ge N\), so an evacuation is always possible.

Note: All formulas are rendered in \(\LaTeX\) format.

inputFormat

The input begins with an integer $T$ ($T\ge 1$) denoting the number of test cases. For each test case:

1. The first line contains three integers $N$, $M$, and $K$.
2. The second line contains $K$ integers: $A_1, A_2, \ldots, A_K$.
3. The third line contains $K$ integers: $S_1, S_2, \ldots, S_K$.
4. Then follow $M$ lines, each containing three integers $u$, $v$, and $w$, describing an undirected edge between nodes $u$ and $v$ with weight $w$.

It is guaranteed that the given graph is connected.

outputFormat

For each test case, output a single integer: the minimum evacuation time $T$.

sample

1
4 4 2
1 4
2 2
1 2 3
2 3 4
3 4 5
1 4 10

5