21033번 - Sending Blessings 다국어

There are N cities connected by N bridges in the country of Sayagueaing. The cities and the bridges are numbered from 1 to N. The i^th bridge connects city A_i and city B_i and can be passed by a total of C_i people before the bridge collapses. It is guaranteed that any pair of cities are connected by a sequence of bridges. It is also guaranteed that any pair of cities are directly connected by at most one bridge.

At the start of every year, one of the N cities wants to send new year blessings to another one of the N cities. Specifically, we will consider the first Q years. At the start of the i^th year, city U_i wants to send new year blessings to city V_i. To do so, the sender city sends as many residents as possible to the recipient city, one resident at a time. Each resident will go from city U_i to city V_i through one or more bridges. The president of Sayagueaing is wondering the number of residents that can reach the recipient city.

Note that at the end of every year, the conditions of the bridges are restored to their original state. In other words, all collapsed bridges will be rebuilt, and the i^th bridge can be passed by a total of C_i people.

Input begins with a line containing two integers: N Q (3 ≤ N ≤ 100 000; 1 ≤ Q ≤ 100 000) representing the number of cities in the country of Sayagueaing and the number of years to be considered, respectively. The next N lines, each contains three integers: A_i B_i C_i (1 ≤ A_i, B_i ≤ N; A_i ≠ B_i; 1 ≤ C_i ≤ 100 000) representing the bridges in the country of Sayagueaing. It is guaranteed that any pair of cities are connected by a sequence of bridges. It is also guaranteed that any pair of cities are directly connected by at most one bridge. The next Q lines, each contains two integers: U_i V_i (1 ≤ U_i, V_i ≤ N; U_i ≠ V_i) representing new year blessings to be sent.

For each year in the same order as input, output in a line an integer representing the number of residents that can reach the recipient city at the start of the year.