Overview

This problem asks us to minimize the “load index”, defined as “total cost + \(K \times\) maximum cost”, among all sets of communication cables that connect all bases (spanning trees).

Although the formula looks complex at first glance, by utilizing the properties of the Minimum Spanning Tree (MST) in graph theory, we can obtain the optimal solution simply by finding a standard minimum spanning tree.

---

Analysis

1. The Optimal Network is a “Tree”

First, let us consider the case where the chosen set of cables \(S\) contains a cycle (loop). Even if we remove one of the highest-cost cables from the cycle, all bases remain connected, and both the “total cost” and “maximum cost” will either decrease or remain unchanged. Therefore, the optimal set of cables \(S\) that minimizes the load index will be a spanning tree without any redundant cycles.

2. Analyzing the Load Index Formula

The load index for a spanning tree \(T\) is expressed by the following formula: $\( \text{Load Index}(T) = \sum_{e \in T} c_e + K \times \max_{e \in T} c_e \)\( Here, the coefficient \)K\( is a non-negative integer (\)K \ge 0\(). If there exists a **spanning tree that simultaneously minimizes both the "total cost \)\sum c_e\(" and the "maximum cost \)\max c_e$“**, that tree will minimize the load index.

3. Powerful Properties of the Minimum Spanning Tree (MST)

In fact, it is a well-known property that the Minimum Spanning Tree (MST), which can be found using algorithms like Kruskal’s algorithm, simultaneously satisfies the following two properties:

1. Minimality of Total Cost: Among all spanning trees, the sum of the edge weights \(\sum c_e\) is minimized.
2. Bottleneck Spanning Tree Property: Among all spanning trees, the maximum edge cost \(\max c_e\) used in the tree is minimized.

Since \(K \ge 0\), a minimum spanning tree—which minimizes both the total cost and the maximum cost—is guaranteed to also minimize their linear combination, the “load index”.

Therefore, this problem reduces to the simple task of “finding the minimum spanning tree of the given graph and calculating the load index from its total cost and maximum edge cost.”

---

Algorithm

To find the minimum spanning tree efficiently, we use Kruskal’s algorithm.

1. Sorting Edges: Sort all cables (edges) in ascending order of their costs.
2. Initializing Union-Find: Initialize a Union-Find data structure of size \(N\) to manage the connectivity of the bases.
3. Greedy Edge Addition:
   • Examine the edges in ascending order of their costs.
   • If the two bases \(u_i, v_i\) connected by the edge do not belong to the same group yet (i.e., they are not connected), we add this edge to our network and merge (union) the two groups in the Union-Find structure.
   • Add the cost of the chosen edge to the total cost mst_weight.
   • Since we process the edges in ascending order, the cost of the last edge added to the tree will automatically be the max_edge_cost (maximum cost).
4. Termination Condition: When the number of chosen edges reaches \(N - 1\), all bases are connected (the minimum spanning tree is complete), so we terminate the search.
5. Output the Answer: Calculate and output mst_weight + K * max_edge_cost.

---

Complexity

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

  • Sorting the edges takes \(O(M \log M)\) time.
  • Union-Find operations (find, union) can be performed in nearly constant time \(O(\alpha(N))\) per operation using optimizations like path compression. Since the main loop runs at most \(M\) times, this part takes \(O(M \alpha(N))\).
  • Therefore, the overall time complexity is bottlenecked by sorting and is \(O(M \log M)\), which is fast enough for the constraints \(N, M \le 2 \times 10^5\).

• Space Complexity: \(O(N + M)\)

  • We use \(O(M)\) memory for the array storing the edge information, and \(O(N)\) memory for the array representing the parents in the Union-Find structure.

---

Implementation Points

• Fast I/O: Since Python can be slow with a large number of inputs, we resolve the I/O bottleneck by reading the entire input at once using sys.stdin.read().split().

• Path Compression in Union-Find: By performing “path compression” (updating parent nodes recursively or iteratively) inside the find function, the complexity per query is reduced to nearly \(O(1)\).

• Updating Maximum Cost: Since we process edges in ascending order of cost, we can correctly maintain the maximum cost among the chosen edges simply by overwriting max_edge_cost with the cost of the newly added edge.

  Source Code

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    edges = []
    idx = 3
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        c = int(input_data[idx+2])
        edges.append((c, u, v))
        idx += 3
        
    # コストの昇順にソート
    edges.sort(key=lambda x: x[0])
    
    # Union-Find
    parent = list(range(N + 1))
    
    def find(i):
        path = []
        while parent[i] != i:
            path.append(i)
            i = parent[i]
        for node in path:
            parent[node] = i
        return i

    def union(i, j):
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            parent[root_i] = root_j
            return True
        return False

    mst_weight = 0
    max_edge_cost = 0
    edges_count = 0
    
    for c, u, v in edges:
        if union(u, v):
            mst_weight += c
            max_edge_cost = c
            edges_count += 1
            if edges_count == N - 1:
                break
                
    ans = mst_weight + K * max_edge_cost
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-high.