Summary

We assign a color number to each vertex of the tree to minimize the sum of the costs \(W_i \times |a-b|\) for each edge.
However, since coloring all vertices with the same color is prohibited, the answer is the “minimum edge weight”.

Observation

First, if there were no constraint that “at least \(2\) distinct colors must be used”, we could color all vertices with the same color, making the cost of all edges \(0\), so the minimum value would be \(0\).

However, this time we must use at least \(2\) distinct colors.

Since the tree is connected, if there are vertices colored with different colors, there must be at least one edge on the path connecting these two vertices where the colors of its two endpoints are different.

Let the weight of this edge be \(W\), and the colors of its endpoints be \(a\) and \(b\). Since \(a \neq b\), we have:

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

Therefore, this edge alone incurs a cost of at least:

\[ W \times |a-b| \geq W \]

Thus, no matter how we color the vertices, the total cost will be at least the weight of the edge where the color changes. In particular, if we let the minimum edge weight of the entire tree be \(\min W_i\), the answer is at least:

\[ \min W_i \]

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

Choose one edge with the minimum weight. Removing this edge from the tree splits the tree into \(2\) connected components.

• Color all vertices in one component with color \(1\).
• Color all vertices in the other component with color \(2\).

Then, the only edge with different colors at its endpoints is the single removed minimum-weight edge.
The cost of this edge is:

\[ \min W_i \times |1-2| = \min W_i \]

All other edges have endpoints of the same color, so their costs are \(0\).

Therefore, the total cost is exactly:

\[ \min W_i \]

which is the minimum possible value.

Naively trying all color assignments would take \(K^N\) ways, which is far too slow to pass.
Also, even if we consider tree DP, since \(K\) can be as large as \(10^8\), storing states for each color is impossible.
In this problem, due to the tree structure and the condition “use at least \(2\) colors”, it is sufficient to look only at the minimum edge weight.

Algorithm

1. Initialize the answer candidate ans with a sufficiently large value.
2. Read the \(M\) edges one by one.
3. For each edge weight \(W_i\), update ans = min(ans, W_i).
4. Finally, output ans.

Complexity

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

Implementation Points

The endpoints of the edges \(u_i, v_i\) are not directly related to the answer.
Only the minimum value of the edge weights \(W_i\) is needed.

Also, since \(K\) is guaranteed to be \(2\) or more, a construction using color \(1\) and color \(2\) is always possible.
Therefore, the specific value of \(K\) only needs to be read and is not used in the calculation.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    long long ans = LLONG_MAX;
    for (int i = 0; i < M; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        ans = min(ans, w);
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.