Countries at War

In 2050, after several attempts by an international body to keep the peace, the third world war breaks out. Industrial, commercial and military secrets force every country to run a highly sophisticated spy service, so every city in the world holds at least one spy from each country. A spy has to reach other spies, informants and their own headquarters while on an assignment. There is no safe channel in wartime, so every message goes out encoded and only its recipient reads what it says.

Spies use the one service that still runs during the war, the mail. Each city has one post office. A letter can go straight to the post office of the destination city, or it can pass through other post offices on the way.

The post office in city $A$ can send a printed letter directly to the post office in city $B$ when the two have a delivery agreement. The agreement fixes the time in hours that the letter needs to travel from $A$ to $B$. An agreement in the opposite direction does not have to exist. Without an agreement between $A$ and $B$, office $A$ relays the letter through as many other offices as it takes.

Some post offices are linked by electronic means such as satellites and optical fiber. Before the war those links reached every office and a letter arrived instantly. Once the war started each country took control of its own electronic communication, so an office can send a letter electronically, that is with no time at all, only to an office in the same country. Offices $A$ and $B$ are in the same country when a printed letter is delivered from $A$ to $B$ and also from $B$ to $A$.

Your spy service holds every delivery agreement in the world. Find the minimum time to send a letter for several pairs of cities.

The input holds several test cases.

The first line of each test case has two integers separated by a space, the number of cities $N$ ($1 \le N \le 500$) and the number of delivery agreements $E$ ($0 \le E \le N^2$). Cities are numbered 1 to $N$.

The next $E$ lines each hold three integers separated by spaces, $X$, $Y$ and $H$ ($1 \le X, Y \le N$, $1 \le H \le 1000$). An agreement sends a printed letter from city $X$ to city $Y$, and that letter arrives $H$ hours later.

The line after that holds the number of queries $K$ ($0 \le K \le 100$). The following $K$ lines each hold two integers separated by a space, $O$ and $D$ ($1 \le O, D \le N$). For each query, determine the minimum time to send a letter from city $O$ to city $D$.

A line where $N$ and $E$ are both 0 ends the input. That line is not a test case.

For each test case print $K$ lines. Line $I$ holds the minimum time in whole hours for query $I$. When there is no way to deliver a letter between the two cities of a query, print Nao e possivel entregar a carta on that line, exactly as written and without quotation marks.

After each test case print one blank line.