Hamiltonian Cycle on a Weighted Tree-Induced Complete Graph

You are given a tree T with n vertices and n-1 undirected, weighted edges. From T we construct an undirected complete graph G(T) on the same n vertices where for every unordered pair of vertices u and v:

• If there is an edge between u and v in T with weight w, then the edge u,v in G(T) has weight \(w\).
• Otherwise the edge weight is defined to be 0.

Let \(w(T)\) be the minimum total weight of a Hamiltonian cycle (a cycle which visits every vertex exactly once and returns to the starting vertex) in G(T).

You are then given q update operations. There are two types of operations:

1. Edge replacement: In the tree T, remove an edge and add a new edge (with a given weight) so that the graph remains a tree.
2. Path update: Given two vertices, update T by adding a given value to the weights of all edges along the unique simple path between these two vertices.

After each operation, you must compute and output the current \(w(T)\) – that is, the minimum Hamiltonian cycle weight in the complete graph G(T) defined as above. In G(T), for any two vertices \(u\) and \(v\), the edge weight is

[ \text{cost}(u,v)=\begin{cases}w(uv) & \text{if }uv \text{ is an edge in }T,\0 & \text{otherwise.} \end{cases} ]

A Hamiltonian cycle’s total weight is the sum of the weights of its edges. Note that if an edge in T is used in the cycle, its weight contributes; otherwise (when using a non‑tree edge) the contribution is 0.

Note: Since the complete graph has many 0‑weight edges, you are allowed to design the cycle arbitrarily to avoid as many tree edges as possible. However, due to the cycle structure each vertex appears with exactly two adjacent vertices, so some tree edges may be forced to be used.

Input Format:

• The first line contains two space­ separated integers: n and q.
• The next n-1 lines each contain three integers u v w meaning that there is an edge between vertices u and v in T with weight w. (Vertices are 1-indexed.)
• The following q lines each describe an update operation in one of the following formats:
• For an edge replacement operation (type 1):
  1 u v x y w
  This means remove the edge between u and v (which is guaranteed to exist) and add a new edge between x and y with weight w. The resulting graph is guaranteed to be a tree.
• For a path update operation (type 2):
  2 u v d
  This means add d to the weights of every edge along the unique simple path in T between vertices u and v.

Output Format:

• After each update operation, output the current value of \(w(T)\) on a separate line.

Constraints and Implementation Note:

You may assume that n and q are small (for example, n ≤ 8) so that a brute‑force solution over all permutations (i.e. trying all Hamiltonian cycles) is feasible.

Your solution must process the updates and then recompute \(w(T)\) after every operation.

inputFormat

The first line contains two integers n and q.

• Next n-1 lines: each containing three integers u v w – an edge in the tree.
• Then q lines: each describing an update operation in one of the following formats:
  • For type 1 (edge replacement): 1 u v x y w
  • For type 2 (path update): 2 u v d

outputFormat

Output q lines. Each line contains the value of \(w(T)\) after the corresponding update operation.

sample

3 1
1 2 10
2 3 5
2 1 3 3

21