405135: GYM101804 H Holidays

Another extended holiday and Lieutenant Calazans is sad because she can't travel again.

There are a lot of places that she lived at and would like to visit again, but all these places are very hard to go to and usually a lot of flight connections are needed to get there. Because of this, she decided to plan ahead the trip for the next holidays.

As the holidays are very short, she doesn't want to make too many flight connections. Besides that, because of the delays on the salary payment of the Lieutenants on the $$$5^{th}$$$ year, she also wants to spend the least amount of money as possible.

As the Lieutenant is very busy organizing the classes to IME++, she asked you to create a program that, given all $$$m$$$ possible flights available, their costs and the list of $$$q$$$ cities she wants to visit on future holidays with the maximum number of flight connections to get there, should say the minimum cost to reach each destination departing from Rio de Janeiro.

Consider that the flights are always available and it's guaranteed that no two flights have the same route, in other words, for any two distinct flights available $$$(a_i, b_i)$$$ and $$$(a_j, b_j)$$$, then $$$(a_i, b_i) \neq (a_j, b_j)$$$.

She will only visit one destination on each holiday then come back to Rio de Janeiro after the holiday. The costs are only for going to the destination so you can let her plan her travel back.

The first line of input contains three integers, $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^3$$$, $$$0 \leq m \leq 10^3$$$) — the number of cities and number of flights.

The next $$$m$$$ lines contains three integers, $$$a_i$$$, $$$b_i$$$ and $$$c_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$, $$$0 \leq c_i \leq 10^3$$$) — the departure city of flight $$$i$$$, the destination city of flight $$$i$$$ and the cost of flight $$$i$$$.

The next line contains one integers, $$$q$$$ ($$$1 \leq q \leq 10^3$$$) — the number destination cities.

The next $$$q$$$ lines contains two integers, $$$d_i$$$ and $$$k_i$$$ ($$$2 \leq d \leq n$$$, $$$0 \leq k \leq n-2$$$) — the destination city she wants to go on the $$$i$$$-th holiday and the maximum number of flight connections to get there.

Rio de Janeiro is always city number $$$1$$$.

For each destination city in the list, print "=]" (without quotes) followed by the minimum cost to reach the destination from Rio de Janeiro, if it's possible to reach it. Otherwise, print "=[" (without quotes).

3 2
1 2 100
2 3 100
2
2 0
3 0

=] 100
=[

5 7
1 2 400
1 3 100
3 2 200
1 4 400
3 4 100
3 5 250
4 5 100
6
5 0
5 1
5 2
2 0
2 1
3 3

=[
=] 350
=] 300
=] 400
=] 300
=] 100