Adera's Mystical Stones

Adera is a puzzle game in the Microsoft Store. In this game, a mysterious stone (\(\text{异象石}\)) acts as a guide to a parallel time-space. The map in the parallel world is a tree with \(N\) nodes and \(N-1\) bidirectional edges connecting them. Initially, there is no stone on the map. Then, during \(M\) time instants, one of the following events occurs:

• Event of type 1: A stone appears on a given node (if a stone already exists at that node, nothing happens).
• Event of type 2: The stone on a given node is destroyed (this event will never be applied to a node without a stone).
• Event of type 3: A query asks for the minimum total length of a set of edges that connects all nodes currently having a stone. In other words, if you consider the unique subtree (or Steiner tree) that connects all nodes with stones, what is the sum of the weights of its edges?

Notes:

• The tree is weighted. For any two nodes \(u\) and \(v\), the distance is defined as \(\text{dist}(u,v) = \text{depth}[u] + \text{depth}[v] - 2 \times \text{depth}[\text{LCA}(u,v)]\), where \(\text{LCA}(u,v)\) is the lowest common ancestor of \(u\) and \(v\).
• If there is zero or one stone, then the answer to a query is 0.

Your task is to process the events and answer all type-3 queries.

inputFormat

The first line contains two integers \(N\) and \(M\) \((1 \leq N, M \leq \text{large})\) representing the number of nodes in the tree and the number of events, respectively.

The next \(N-1\) lines each contain three integers \(u\), \(v\), and \(w\) indicating that there is an edge between node \(u\) and node \(v\) with weight \(w\).

The following \(M\) lines each describe an event in one of the following formats:

• 1 x: A stone appears on node \(x\).
• 2 x: The stone on node \(x\) is destroyed.
• 3: Query the minimum total length required to connect all nodes with a stone.

outputFormat

For each event of type 3, output a single line containing the answer — the minimum total length of edges required to connect all nodes currently having a stone.

sample

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

0
0
4