Summary

This problem asks us to assign colors from \(1\) to \(K\) to a tree-structured map such that at least \(2\) different colors are used, while minimizing the total cost over all edges, where the cost of each edge is \(W_i \times |a-b|\).

In conclusion, the answer is the minimum of the edge weights \(W_i\).

Analysis

First, if we color all regions with the same color, \(|a-b|=0\) holds for all edges, so the cost would be \(0\).

However, in this problem, we must use at least \(2\) different colors, so we cannot paint all vertices with the same color.

Here is an important property.

Since a tree is connected, if both endpoints of every edge have the same color, then all vertices must have the same color.
Therefore, if we use at least \(2\) different colors, there must be at least one edge whose endpoints have different colors.

If the colors of the endpoints of some edge \(i\) are different, since the color IDs are integers, we have:

\[ |a-b| \geq 1 \]

Therefore, this edge alone incurs a cost of at least

\[ W_i \times 1 = W_i \]

Thus, no matter how we color the vertices, the total cost will be at least

\[ \min_i W_i \]

Next, we show that this lower bound can actually be achieved.

Let \(e\) be the edge with the minimum weight. Removing this edge \(e\) from the tree splits it into two connected components.

We color one connected component with color \(1\) and the other with color \(2\).

Then, the only edge with different endpoint colors is exactly edge \(e\).
The cost of this edge is

\[ W_e \times |1-2| = W_e \]

Since \(W_e\) is the minimum edge weight, the total cost is

\[ \min_i W_i \]

Therefore, the answer is simply the minimum edge weight.

Trying to naively consider the color of each vertex or perform tree DP is impractical because \(K\) can be as large as \(10^8\).
However, from the above analysis, we do not need to consider the concrete assignment of colors; we only need to find the minimum value of the edge weights.

Algorithm

1. Read \(M\) edges from the input.
2. Check the weight \(W_i\) of each edge.
3. Find the minimum of these weights.
4. Output the minimum value.

The answer is

\[ \min_{1 \leq i \leq M} W_i \]

Complexity

• Time Complexity: \(O(M)\)
• Space Complexity: \(O(M)\)

Since the entire input is read as a list, the space complexity of this implementation is \(O(M)\).
However, if we read the edges sequentially, the auxiliary space complexity can be reduced to \(O(1)\).

Implementation Details

In this implementation, the entire input is read as a sequence of integers.

data = list(map(int, sys.stdin.buffer.read().split()))

The first \(3\) elements are \(N, M, K\), so the edge information starts from data[3].
Each edge is represented by \(3\) integers:

u v w

so the weight is located at index idx + 2 for each edge.

The vertex indices \(u, v\) and the number of colors \(K\) are not used directly to calculate the answer.
Only the minimum value of the edge weights \(W_i\) is required.

Source Code

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
m = data[1]

ans = 10**18
idx = 3
for _ in range(m):
    w = data[idx + 2]
    if w < ans:
        ans = w
    idx += 3

print(ans)

---

This editorial was generated by gpt-5.5-high.