10453: #2110. 「JLOI2015」管道连接

小铭铭最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。

该部门有 $n$ 个情报站，用 $1$ 到 $n$ 的整数编号。给出 $m$ 对情报站 ui,viu_i, v_iu​i​​,v​i​​ 和费用 wiw_iw​i​​，表示情报站 uiu_iu​i​​ 和 viv_iv​i​​ 之间可以花费 wiw_iw​i​​ 单位资源建立通道。

如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就建立了通道连接。形式化地，若 uiu_iu​i​​ 和 viv_iv​i​​ 建立了通道，那么它们建立了通道连接；若 uiu_iu​i​​ 和 viv_iv​i​​ 均与 tit_it​i​​ 建立了通道连接，那么 uiu_iu​i​​ 和 viv_iv​i​​ 也建立了通道连接。现在在所有的情报站中，有 $p$ 个重要情报站，其中每个情报站有一个特定的频道。

小铭铭面临的问题是，需要花费最少的资源，使得任意相同频道的情报站之间都建立通道连接。

输入格式

第一行包含三个整数 $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。