Little B is playing a treasure hunt game. The map for this game consists of $N$ villages and $N-1$ roads, such that there is exactly one path between any two villages. At the start of the game, the player can choose any village to teleport to instantly, and then move freely along the roads on the map. If the player reaches a village containing a treasure, it is considered that the treasure in that village has been found. The game continues until all treasures have been found and the player returns to the village they initially teleported to.
Little B wants to evaluate the difficulty of this game, so he needs to know the minimum distance the player must travel to find all treasures. However, the treasures in this game change frequently; sometimes a treasure suddenly appears in a village, and sometimes a treasure in a village suddenly disappears. Little B needs to update the data constantly, but he is too lazy to calculate it himself, so he is asking for your help.
To simplify the problem, we assume that initially, there are no treasures in any of the villages.
Input
The first line contains two integers $N$ and $M$, where $M$ is the number of treasure changes.
The next $N-1$ lines each contain three integers $x$, $y$, and $z$, representing a road of length $z$ between villages $x$ and $y$.
The next $M$ lines each contain an integer $t$, representing an operation to change the treasure status of village $t$. If there was no treasure in village $t$ before this operation, there will be a treasure after the operation; if there was a treasure in village $t$ before this operation, there will be no treasure after the operation.
Output
Output $M$ lines, each containing an integer. The integer on the $i$-th line represents the minimum distance the player needs to travel to find all treasures after the $i$-th operation. If there is only one village with a treasure, or if there are no treasures in any village, output 0.
Examples
Input 1
4 5 1 2 30 2 3 50 2 4 60 2 3 4 2 1
Output 1
0 100 220 220 280
Constraints
| Test Case ID | $N$ Range | $M$ Range | Other |
|---|---|---|---|
| 1 | $1 \le N \le 100$ | $1 \le M \le 100$ | None |
| 2 | $1 \le N \le 100$ | $1 \le M \le 100$ | None |
| 3 | $1 \le N \le 1000$ | $1 \le M \le 1000$ | None |
| 4 | $1 \le N \le 1000$ | $1 \le M \le 1000$ | None |
| 5 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | The $N$ villages and $N-1$ roads form a chain |
| 6 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | The $N$ villages and $N-1$ roads form a chain |
| 7 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | The $N$ villages and $N-1$ roads form a chain |
| 8 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | The first change is to village 1, and village 1 does not change again |
| 9 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | The first change is to village 1, and village 1 does not change again |
| 10 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | The first change is to village 1, and village 1 does not change again |
| 11 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
| 12 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
| 13 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
| 14 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
| 15 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
| 16 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
| 17 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
| 18 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
| 19 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
| 20 | $1 \le N \le 100000$ | $1 \le M \le 100000$ | None |
For all data, $1 \le z \le 10^9$.