Supply Station Optimization

In this problem, a strategy game map is represented as a tree with n nodes (empty lands) connected by n-1 weighted edges. There is a unique path between any two nodes. Initially, there are no armies on any node. During the game, you will execute operations of two types:

• Update Operation: Increase or decrease the number of troops on a given node.
• Query Operation: Determine the minimum daily supply cost by selecting exactly one node as a supply station.

If the supply station is placed at node \(u\) and node \(v\) has \(d_v\) troops, then the daily cost to supply armies is given by:

\(\sum_{v=1}^{n} d_v \times \text{dist}(u,v)\)

where \(\text{dist}(u,v)\) denotes the sum of weights along the unique path between \(u\) and \(v\). Your task is to process a sequence of operations and, for every query, output the minimum possible supply cost over all choices of the supply station.

Note: You may assume that all update operations keep the troop count non-negative.

inputFormat

The first line contains two integers n and q representing the number of nodes and the number of operations, respectively.

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

The following q lines each describe an operation. Each operation is in one of the following two forms:

• U u k: Update the troop count at node u by adding k (which may be negative) to its current value.
• Q: Query the minimum supply cost achievable by placing the supply station at the optimal node.

All nodes are numbered from 1 to n.

outputFormat

For each query operation, output a single line containing one integer—the minimum possible daily supply cost.

sample

3 5
1 2 1
2 3 2
Q
U 2 10
Q
U 1 5
Q

0
0
5