All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Curious Costs
Tag(s):

Medium

Problem
Editorial
Analytics

The government of cryptLand has banned the use of online maps in the country due to fear of tracking by various enemy agencies. So now, it has to come up with a new indigenous navigation system. As a part of this, it needs a subroutine that can tell the least cost to travel from one city to another in cryptLand.

There are N cities in cryptLand and they are connected by M unidirectional roads and metro. The cost to travel between some cities directly (without any intermediate stops) is known beforehand. While travelling on roads, the citizens have to pay money to the government. Since metros are public transport and newly started, the government gives you money for travelling through them.

The government has to first check if the travel network is valid or not. The entire network is invalid even if a single pair of cities exist such that it is not possible to find the unique shortest cost of travelling between the cities.

If the network is valid, then the citizens of cryptLand give a large number of queries to the government to ensure the optimality of designed algorithm. The government must answer these queries really quickly.

Fulfil your duty as the minister of algorithms and answer the queries of people!

Input

The first line contains two integers N and M, the number of cities and the number of unidirectional roads/metro lines.

The next M lines each contain three integers U V W . W is the cost of travelling from city U to city V. If W is positive, then there is a road from city U to city V. If W is negative, then there is a metro link from city U to city V . Note that it is not necessary that there is a direct link from V to U since the roads and metros are unidirectional. This link is unique i.e. there is no other direct link from U to V. Also, U and V are distinct.

The next line contains an integer Q denoting the number of queries asked by the citizens.

The next Q lines contain one query each. Each query is of the form X Y which means that you must report the unique shortest cost to travel from X to Y using any number of intermediate cities.

Output

If the travel network is invalid, then just print "Not Possible" (without quotes).

If it is valid, then output 1 line for each query X Y. If there does not exist a way to reach from X to Y, then print "No Route" (without quotes) for this query. Otherwise, print the unique shortest cost to travel from X to Y.

Constraints

1 <= N <= 2000

1 <= M <= min ( 10000 , n(n-1) )

1 <= U, V, X, Y <= N

1 <= Q <= min ( 105, n(n-1))

-2,00,000 <= W <= 2,00,000

SAMPLE INPUT
6 7
1 2 2
2 3 -1
3 1 4
3 4 2
3 5 -3
6 4 1
6 5 -4
5
1 3
1 2
3 6
4 6
2 5
SAMPLE OUTPUT
1
2
No Route
No Route
-4
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

IISc Bangalore

Challenge Name

Programmers' Parliament

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications