Mittal lives in the Niti Colony. The colony has N houses numbered from 1 to N. There are M bidirectional roads in the colony for travelling between houses. There might be multiple roads between two houses.
Mittal lives in the house with index 1. He has friends in all houses of the colony. He is always wanting to visit them to play. But his mom is really strict. She only allows him to go out for K units of time. This time includes the time taken to go to his friend's house , play with the friend and time taken to come back home.
You are given Q queries. In each query, Mittal wants to go to his friend in house A , given K units of time. Help him find the maximum time that he can play.
If K units of time is not sufficient to visit his friend and return back, Mittal will not go and playing time will be zero.
Input:
First line contains an integer T. T test cases follow.
First line of each test case contains two space-separated integers N, M
Next M lines contain three space-separated integers X, Y and C, denoting that there is Bidirectional road between house X and house Y with cost C.
Next line contains an integer Q
Following Q lines describe the queries. Each query contains two space-separated integers A and K.
Output:
Print the answer to each query in a new line.
Constraints:
1 ≤ T ≤ 10
1 ≤ N, Q ≤ 104
1 ≤ M ≤ 105
1 ≤ X, Y, A ≤ N
1 ≤ K ≤ 104
1 ≤ C ≤ 1000
