Euler's flat in Zurich P84723

Recently, Gauss has moved to Zurich, and his friend Euler, who used to live in Switzerland, has offered him to move into his empty flat. However, Gauss has found that the flat is a complete mess, so he has to clean every single part of it.

Euler’s flat can be modeled as an undirected graph with n vertices, one for each spot. The graph has m edges, each joining two spots that are a distance ℓ apart. In addition, k spots contain a piece of furniture of weight w. Note that the ℓs and the ws may be different.

To clean every spot u with furniture, Gauss needs to first clear u, moving furnitures around in such a way that no two pieces are in the same spot at the same time. The effort to move a piece of weight w along a distance ℓ is just w · ℓ. After cleaning u, Gauss will move back all furniture to their original place before cleaning another spot. What is the minimum effort to leave each u empty? (Do not count the effort to move the furniture back.)

Input

Input consists of several cases with only integer numbers. Every case begins with n, m and k, followed by m triples u, v, ℓ denoting an edge between spots u and v of length ℓ, followed by k pairs u, w meaning that the spot u contains a piece of furniture of weight w.

You can assume 2 ≤ n ≤ 2 · 10⁴, 1 ≤ m ≤ 5n, and 0 < k < n. Spots are numbered from 0 to n − 1. All ℓs and ws are between 1 and 10⁵. The graph is connected, without loops or parallel edges. No spot contains more than one piece of furniture.

Output

For each case, and for each spot u with furniture, in increasing order of u, print the minimum effort to move the furniture to clean u. Print a line with 10 dashes after every case.