题意：

　　n个城市，m条路，每条路有个危险值，要使得从s走到t的危险值最小。回答q个询问，每个询问有s和t，要求输出从s到t最小的危险值。（5万个点，10万条边）

Sample Input

4 5

1 2 10

1 3 20

1 4 100

2 4 30

3 4 10

2

1 4

4 1

 

2 1

1 2 100

1

1 2

Sample Output

20

20

 

100