Minimum Toll Fee

You are given an undirected graph representing a network of n cities and the roads connecting them. Each road has an associated toll fee. The graph is given by n (the number of cities) and n-1 edges. However, it is possible that not all cities are connected.

Each edge is described by three integers: u, v and w, indicating a road between cities u and v with a toll fee of w. You are also given q queries. Each query consists of two integers a and b asking for the minimum total toll fee required to travel from city a to city b.

The toll fee for a route is the sum of the toll fees for each road on that route. In mathematical terms, if a route consists of roads with toll fees \( w_1, w_2, \dots, w_k \), then the total toll fee is given by:

\[ \text{Total Fee} = \sum_{i=1}^{k} w_i \]

If there is no path between the two given cities, output inf.

inputFormat

The input is read from standard input and is formatted as follows:

• The first line contains an integer n, the number of cities.
• The next n-1 lines each contain three integers u, v, and w describing a road between cities u and v with toll fee w.
• The following line contains an integer q, the number of queries.
• The next q lines each contain two integers a and b representing a query to find the minimum toll fee from city a to city b.

outputFormat

For each query, output the minimum toll fee on a separate line. If no path exists between the queried cities, output inf.

## sample

5
1 2 3
1 3 4
2 4 5
2 5 6
3
1 4
4 5
3 5

8
11
13

</p>