City Driving

You recently started spending your free time in San Francisco and realized that driving around the city is a huge pain. There are only $N$ locations that interest you, so you decide to make your driving easier. Because you have no GPS and cannot memorize many routes, you write down directions and travel times between $N$ pairs of locations. Each route is bidirectional (it takes the same time in either direction), and using only these routes you can travel between any two locations.

Now you are planning your weekend trips and, for $Q$ pairs of locations, you need to find the fastest way to travel between them using only the routes you wrote down.

The input contains multiple test cases.

Each test case begins with a line containing a single integer $N$ ($3 \le N \le 100{,}000$), the number of locations, which is also the number of routes.

Each of the next $N$ lines contains three integers $u$, $v$, and $w$ ($1 \le w \le 1{,}000$): a route connecting locations $u$ and $v$ (0-indexed) that takes time $w$ in both directions.

The next line contains a single integer $Q$ ($1 \le Q \le 10{,}000$), the number of queries.

Each of the next $Q$ lines contains two integers $u$ and $v$: find the minimum time to travel from location $u$ to location $v$.

The input ends with a line containing $N = 0$, which should not be processed.

For each test case, print $Q$ lines. The $i$-th line contains a single integer: the minimum time to travel between the $i$-th queried pair of locations $u$ and $v$.