Description

You are given all neighbourhoods in Sofia and the distances between them. A thunderstorm is raging above the city with lightning strikes falling all around.
When a lightning falls, it damages all connected neighbourhoods, but the damage halves with each jump (integer division). The lightning always jumps to a neighbourhood that has the smallest distance to any neighbourhood already damaged. Note that a lightning doesn’t necessarily forks only at its tail. Also, the same lightning cannot damage the same neighbourhood twice.
Consider the example: lightning falls on the 1st neighbourhood with full force, then jumps to the 3rd (distance to 1st is smallest) with its damage halved. After that the nearest one is the 2nd (distance from first is 10, damage also halved) and lastly it jumps to the 4th from the 2nd (15 < 20) with initial damage divided by 2 and then divided by 2 again.

Your job is to find the condition of the most heavily damaged neighbourhood after multiple strikes on top of different city neighbourhoods, so a team of highly skilled technicians can be dispatched.
Input
• The first line holds an integer n – the number of neighbourhoods
• On the second line, you will receive the number m – the number of distances
• On the third line, l – the number of lightnings
• At the next m lines, you will receive the distances: {from neighbourhood} {to neighbourhood} {distance}
• At the next l lines, you will receive the lightning strikes: {neighbourhood} {damage} • Neighbourhood will always be numbered from 0 to N – 1
Output
• Print the condition of the most heavily damaged neighbourhood
Constraints
• Number of neighborhoods will be an integer in the range [0…5000]
• Number of connections will be an integer in the range [0…10000]

• Number of lightning strikes will be an integer in the range [0…1000]
• Distance between neighborhoods will be a unique integer in the range [0…100000]
• Lightning damage will be an integer in the range [0…1000]
• Time limit: 200 ms. Allowed memory: 32 MB
Examples
Input Output Visual Comment
5
5
2
0 1 10
1 4 20
2 4 30
0 2 35
0 3 50
0 40
4 20 45 There are two lightnings.

First lightning (0 40):

0 → 40
3 → 20
1 → 20
4 → 10
2 → 5

Second lightning (4 20):

4 → 20
2 → 10
1 → 10
0 → 5
3 → 2

0 is most heavily damaged

Input Output Visual
10
8
3
0 1 5
1 2 4
1 3 6
2 3 3
2 5 7
2 4 2
7 6 8
7 8 1
2 100
0 200
9 100 225