Mr. Tonmoy is a service holder of BUET (British Ultramodern Energy Technique) Company. He liked his boss very much. But, recently, he hates him as he (The Boss) ordered him to go to Bangladesh. Tonmoy knows that Bangladesh is a country of Traffic Jam and no Government has yet taken this serious problem into account. All the people of that country matched themselves with this annoying Jam. At first, Tonmoy wanted to avoid the order but the boss insisted him visiting Bangladesh. Well, as there is no way to escape, Tonmoy is planning to take the Laptop and a map of roads of Bangladesh with him. Now your task is to help Tonmoy to write a good program that will take different roadmaps of Bangladesh and help him to determine the shortest road having shortest time to go from one place to another so that he can avoid that terrible jam. Input Input consists of several input blocks. The first line in the input file consists of the number of cases to solve. Next lines will consist of several roadmaps. The first line of a block consists two integers x and y indicating the number of distinct places and the number of roads exists between them. Places are numbered starting from 1. The next y lines consists of four integers a, b, c, d indicating two ends of a road, time and roadlength respectively. Next line contains number of queries q for that particular map. Next q lines contains two integers, source and destination. You are to compute shortest distance having shortest time from the source to destination for each query. None of the roads of Bangladesh are one ways. Consecutive blocks are separated by a blank line. There are at most 25 roads in a road map. Output For each query you correct program should output one of the two cases , in a separate line. 1. ‘No Path.’ 2. ‘Distance and time to reach destination is m & n.’ where m and n indicate distance and time to reach from source to destination respectively. Consecutive outputs should be separated by a blank line. For clarification check the following sample inputs and corresponding outputs. Sample Input 2 32 1225 2336 1 13 13 42 1252
2/2 2363 1 14 Sample Output Distance and time to reach destination is 11 & 5. Distance and time to reach destination is 11 & 5. No Path.