「亲爱的观众朋友们，钟表小子和他的伙伴们又要和大家见面啦！」
「在上一集中，石头老板发现了美梦小镇藏有丰富的资源，开始抢夺美梦小镇的统治权。钟表小子联合哈努兄弟与折纸小鸟，将石头老板和他的可恶下属赶出了美梦小镇。」
「石头老板心有不甘，聚集一帮打手誓要踏平美梦小镇。钟表小子将在这一集中面临史上最大危机！」
「钟表小子会用怎样的计谋突出重围？又会有什么新伙伴加入他的队伍？敬请欣赏最新一集『美梦小镇历险记』！」

美梦小镇有 n 个路口，和 m 条连接这些路口的街道。第 i 条街道连接第 x[i],y[i] 两个路口，距离是 w[i] 。

这些路口间，有 k 对路口是热门交通线，第 i 条热门交通线的起点终点分别为第 a[i],b[i] 个路口。

钟表小子可以施展钟表戏法，使得最多一条街道的距离变为 0 。

设第 x,y 路口间的经过若干街道的最短距离为 dis(x,y) ，求 k 条热门交通线的最短距离之和，即 dis(a[1],b[1])+dis(a[2],b[2])+...+dis(a[k],b[k]) ，最小是多少。

第一行包含三个整数 n,m,k (2≤n≤1000, n-1≤m≤min(1000,n*(n-1)/2), 1≤k≤1000) ，表示路口数、街道数、热门交通线数。
接下来 m 行，每行包含三个整数 x[i],y[i],w[i] (1≤x[i],y[i]≤n, x[i]≠y[i] , 1≤w[i]≤1000)，表示第 i 条街道连接第 x[i],y[i] 两个路口，距离是 w[i] 。
接下来 k 行，每行包含两个整数 a[i],b[i] (1≤a[i],b[i]≤n)，表示第 i 条热门交通线的起点终点分别为第 a[i],b[i] 个路口。

保证图是连通的，且不存在重边。

一行包含一个整数，表示答案。

样例1：
6 5 2
1 2 5
2 3 7
2 4 4
4 5 2
4 6 8
1 6
5 3

样例2：
5 5 4
1 2 5
2 3 4
1 4 3
4 3 7
3 5 2
1 5
1 3
3 3
1 5

样例1：
22

样例2：
13

样例解释
样例1如下所示：

你可以选择修改 <2,4> 或 <4,6> 边。

样例2如下所示：

你可以选择修改 <3,4> 边。