Minimum Travel Cost with Damaged Railways

You are given a transportation network of n cities and m bidirectional railway tracks. Each track connects two different cities and has an associated travel cost. Unfortunately, some railway tracks are damaged, and they cannot be used for travel.

Your task is to compute the minimum travel cost from the capital city (city 1) to every other city using only the available (non-damaged) railway tracks. If a city is unreachable from the capital, output -1 for that city.

The shortest path calculation is based on the following recurrence formula in LaTeX: \[ d[v] = \min\bigl(d[v],\; d[u] + w_{uv}\bigr) \quad \text{for each edge } (u,v)\text{ with weight } w_{uv}, \] where \(d[v]\) is the shortest distance from the capital to city \(v\).

Note: The railway network is undirected. Damaged railway tracks, as specified in the input, should be entirely ignored when computing the travel costs.

inputFormat

The first line contains three integers separated by spaces: n (number of cities), m (number of railway tracks), and k (number of damaged tracks).

The next m lines each contain three integers u, v, and w, representing a railway track connecting city u and city v with cost w.

The following k lines each contain two integers representing a damaged railway track between two cities.

outputFormat

Output a single line containing n - 1 space-separated integers. The i^th integer (for 2 ≤ i ≤ n) is the minimum travel cost from city 1 to city i. If a city is unreachable, output -1 for that city.

5 6 1
1 2 4
1 3 7
2 3 1
2 4 2
3 4 3
4 5 5
2 3

4 7 6 11