Sister Cities

Indonesia has $N$ cities numbered from 0 to $N-1$, and $M$ two-way roads numbered from 0 to $M-1$. Each road connects two different cities. Road $i$ connects city $U_i$ and city $V_i$, and a car needs $W_i$ units of gasoline to travel along it. Every pair of cities is connected by a series of roads.

For the next $Q$ days, one pair of cities will try to become sister cities each day. On day $j$, city $X_j$ tries to become a sister city of city $Y_j$. To do this, city $X_j$ sends a delegation by car to city $Y_j$, and city $Y_j$ sends a delegation by car to city $X_j$.

To prevent congestion, two cars must never meet. Specifically, two cars must never be in the same city at the same time. Also, two cars must not travel the same road in opposite directions at the same time. In addition, a car that enters a road must drive to the other end and reach the destination. In other words, a car cannot turn around in the middle of a road. However, a car may visit the same city or the same road more than once. A car may also wait in any city at any time.

A large fuel tank makes a car expensive, so the two cities want routes that minimize the maximum fuel tank capacity of the two cars. Every city has a gas station with unlimited gasoline. Therefore, the fuel tank capacity a car needs is the largest amount of gasoline required on any road the car uses.

• $2 \le N \le 100000$.
• $N-1 \le M \le 200000$.
• $0 \le U_i < V_i < N$.
• At most one road connects any two cities.
• Any two cities can reach each other by one or more roads.
• $1 \le W_i \le 10^9$.
• $1 \le Q \le 200000$.
• $0 \le X_j < Y_j < N$.