Contents

• # For Solution

There are NN cities (numbered from 11 to NN) and MM bidirectional roads. The ithith of these roads connects the cities AiAi and BiBi and has a length of DiDi Km.

There are only KK cities that have a hospital for corona testing. The cost of corona testing may be different in different cities. For each city, we want to know the minimum cost that needs to be spent to test a corona sample. If city you are in contains a hospital and you choose to test in that hospital itself, then the cost incurred is the cost of corona test in that hospital. Otherwise, if you choose to test in a hospital in another city, then an additional transportation cost is also incurred (Assuming Rs.1 per Km).

So from a city ii, if you choose to send a sample to city jj, then the total cost incurred will be Cj+D(i,j)Cj+D(i,j). Here CjCj denotes the cost of corona testing in a hospital situated in city jj and D(i,j)D(i,j) denotes the minimum distance between city ii and jj via some road network.

Output the minimum money that should be spent by a person in each of the NN cities for testing a corona sample.

It is guaranteed that there is a path from every city to every other city. Also, there is at most one road between any pair of cities (i.e. no multiple edges). There are no roads from one city to itself (i.e. no self-loops).

Note: Since the inputs and outputs are large, prefer using fast input-output methods.

### Input Format

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• Each testcase contains K+M+1K+M+1 lines of input.
• The first line of each test case contains three space-separated integers N,M,KN,M,K.
• KK lines follow. For each valid ii, the ithith of these lines contains two space-separated integers xi,Cixi,Ci which denotes that there is a hospital in the xthixith city and the cost of corona testing in that hospital is CiCi. There is at most one hospital in a city i.e. all xixi-s are distinct.
• Next MM lines follow. For each valid ii, the ithith of these lines contains three space-separated integers Ai,Bi,DiAi,Bi,Di, which denotes that there is a bidirectional road between City AiAi and City BiBi of length DiDi Km.

### Output Format

For each test case, print a single line containing NN space-separated integers, where the ithith integer denotes the minimum cost of corona testing if you are in the ithith city.

### Constraints

• 1T40001≤T≤4000
• 2N21052≤N≤2⋅105
• 1M41051≤M≤4⋅105
• 1KN1≤K≤N
• 1xi,Ai,BiN1≤xi,Ai,Bi≤N for each valid ii
• 1Ci1091≤Ci≤109 for each valid ii
• 1Di1091≤Di≤109 for each valid ii
• Sum of NN over all test cases does not exceed 21052⋅105
• Sum of MM over all test cases does not exceed 41054⋅105
• All xixi-s in a testcase are distinct.
• It is guaranteed that there is a path from every city to every other city.
• It is guaranteed that there are no self loops and multiple edges.

### Sample Input 1

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


### Sample Output 1

5 10 19
5 6 15


### Explanation

Test case 11: The hospitals are situated at cities 11 and 22 with their costs being 55 and 10 respectively. For city 11 it is optimal to test the sample in its own hospital bearing a total cost of 55. For city 22 it is again optimal to test the sample in its own hospital bearing a total cost of 1010. For city 33 it is optimal to test the sample in the hospital at city 22 which incurs the traveling cost of 99 and hospital cost of 1010, so the total cost is 10+9=1910+9=19.

Test case 22: For city 22, it is optimal to test the sample in hospital at city 11 which incurs a traveling cost of 11 and hospital cost of 55, so the total cost is 1+5=61+5=6.