第一行包含三个整数 $n,m,p$，表示情报站的数量，可以建立的通道数量和重要情报站的数量。

接下来 $m$ 行，每行包含三个整数 ui,vi,wiu_i, v_i, w_iu​i​​,v​i​​,w​i​​，表示可以建立的通道。最后有 $p$ 行，每行包含两个整数 ci,dic_i, d_ic​i​​,d​i​​，表示重要情报站的频道和情报站的编号。

输出一行一个整数，表示任意相同频道的情报站之间都建立通道连接所花费的最少资源总量。

样例输入

5 8 4
1 2 3
1 3 2 
1 5 1
2 4 2
2 5 1
3 4 3 
3 5 1
4 5 1
1 1
1 2
2 3
2 4

样例输出

4

样例解释

选择 $(1,5);(3,5);(2,5);(4,5)$ 这四对情报站连接。

对于 $100\%$ 的数据，0<ci≤p≤10, 0<ui,vi,di≤n≤1000, 0≤m≤3000, 0≤wi≤200000 < c_i \leq p \leq 10, \ 0 < u_i, v_i, d_i \leq n \leq 1000, \ 0 \leq m \leq 3000, \ 0 \leq w_i \leq 200000<c​i​​≤p≤10, 0<u​i​​,v​i​​,d​i​​≤n≤1000, 0≤m≤3000, 0≤w​i​​≤20000。