New update is available. Click here to update.

Last Updated: 6 Jul, 2021

Difficulty: Hard

```
The first line contains one positive integer ‘T’, denoting the number of test cases, then ‘T’ test cases follows
The first line of each test case contains three integers ‘N’ ‘M’ and ‘Q’, denoting the number of cities, the number of rivers and number of travel.
The next ‘M’ lines of each test case contains three space-separated integers ’u’ , ‘v’ and ‘w’, denoting connection between cities ‘u’ and ‘v’ where river flow from ‘u’ to ‘v’ and energy required against flow is ‘w’.
The next ‘Q’ lines of each test case contain two integers ‘x’ and ‘y’, denoting each travel from ‘x’ to ‘y’.
```

```
The first and the only line of each test case contains one integer ‘X’, denoting the minimum energy required to complete his journey using his special power ( he may not use his special power).
Output of each test case will be printed on a separate line.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N, M, Q <= 1000
0 <= u, v <= N - 1, u != v
0 <= ‘x’, ‘y’ <= N - 1
Time Limit: 1 sec.
```

SIMILAR PROBLEMS

Plantation

Posted: 9 Sep, 2022

Difficulty: Moderate

COUNT ISLANDS

Posted: 14 Sep, 2022

Difficulty: Moderate

Capturing Grid

Posted: 14 Sep, 2022

Difficulty: Moderate

Rotting Oranges

Posted: 15 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: