You are now in a big factory. The factory could be recognized as a graph with n vertices and m edges. Every edge has its length. You have k missions to do. The i-th mission is going to vertex , picking a block and then sending it to vertex . You should complete the missions in the order from 1-st to k-th. Initially you are standing at vectex 1.

You have a gun in your hand. When you are at some vertex u, you could shoot the gun at the ground, and then a portal will be built at vertex u. When there are two portals in the factory, assuming they are at u and v, you could transfer between u and v with no cost(just like an edge connecting u and v with length 0).

You also have a remote controller in your hand. It allows you to close a portal whenever you want and wherever you are(closing one portal at a time, not all portals at the same time). What's more, there could be at most two existing portals. So if you want to create another portal when there exists two, you must use your controller to close one before you create.

You need to find the minimum distance you have to walk in order to complete all k missions.

First line contains three positive integers n, m, k separated by spaces.

Next m lines, each contains three integers , , , indicating a bidirectional edge connecting vertex  and  with length .

Next k lines, each contains two intergers , indicating the begin and the end of the i-th mission.













The graph is guaranteed to be connected.

Output one integer indicating the minimum distance.

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

5

Solution for sample 1: walk from 1 to 5, create portals at 2 and 4 when passing by. And then walk from 5 to 4, then you could use portals to complete the second mission.

6 10 3
1 1 6
5 6 9
3 5 8
1 4 1
2 4 7
6 6 10
1 4 2
6 5 10
3 5 2
3 1 9
1 5
2 5
4 3

28

6 10 3
1 1 3
3 1 1
6 2 3
1 6 10
4 1 1
3 1 2
5 6 9
5 4 10
6 3 4
3 4 4
3 5
3 6
6 5

16