전력난

• 불이 켜진 길의 길이가 최소가 되어야 한다. 이것은 최소 신장 트리 (Minimum Spanning Tree / MST) 알고리즘으로 바로 구할수 있다.
• 문제에서 요구하는 것은 불이 켜진 길의 길이가 아니라, 불이 켜진 길을 제외한 나머지 길의 길이이므로, 전체 길의 길이의 합에서 불이 켜진 길의 길이의 합을 빼주면 된다.
• 시간복잡도는 최소 신장 트리 (Minimum Spanning Tree / MST)를 구하는데에 드는 O(ElogV)이다.

"""Solution code for "BOJ 6497. 전력난".

- Problem link: https://www.acmicpc.net/problem/6497
- Solution link: http://www.teferi.net/ps/problems/boj/6497

Tags: [Minimum spanning tree]
"""

import sys
from teflib import graph as tgraph


def main():
    while (line := sys.stdin.readline().rstrip()) != '0 0':
        m, n = [int(x) for x in line.split()]
        edges = [
            [int(x) for x in sys.stdin.readline().split()] for _ in range(n)
        ]

        total_cost = sum(z for x, y, z in edges)
        mst_edges = tgraph.minimum_spanning_tree(edges, m)
        mst_cost = sum(z for x, y, z in mst_edges)

        print(total_cost - mst_cost)


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.minimum_spanning_tree