406557: GYM102439 K Innovations

Berland  — an independent state from $$$n$$$ cities, some of which are connected with $$$n-1$$$ roads in such a way that it is possible to reach any city from any other city using these roads. The time required to traverse a road using a car is known.

Administration of Berland calculated the minimal time to drive from one city to the other city, for all the pairs of cities and are horrified how old the roads are. It is time to make innovations! Specifically, $$$m$$$ times the administration takes two cities $$$u, v$$$ and replaces all the roads on the shortest path from $$$u$$$ to $$$v$$$ with innovative ones. If the road required $$$w$$$ time to drive before, then after the replacement of this road the time will be $$$\lfloor \sqrt{w} \rfloor$$$. After some road became innovative, it can become even more innovative. Other words, one road can be updated several times.

Unfortunately, the renovation will be held by you. Calculate the sum of the shortest paths between all pairs of cities before the innovations and after each replacement of path. As these sum can be large, print it modulo $$$10^9 + 7$$$.

The first line contains two integers $$$n, m$$$  — denoting the number of cities and queries, respectively.

Each of the following $$$n-1$$$ lines contains three integers $$$u, v, w$$$  — denoting the cities connected by road and the time required to drive this road.

Each of the following $$$m$$$ lines contain two integers $$$u, v$$$  — denoting that innovations are held on the path between them.

$$$$$$1 \le n, m \le 2\cdot10^5$$$$$$ $$$$$$1 \le u, v \le n, 1 \le w \le 10^6$$$$$$

Print $$$m+1$$$ lines, each of them should contain a single integer  — initial sum and $$$m$$$ answers to the queries modulo $$$10^9 + 7$$$.

5 3
1 2 4
2 3 4
1 4 9
1 5 16
1 5
1 3
1 4

140
92
72
48