연애 혁명 ( 27498 백준)

 다른 문제와 다르게 MST가 안 생기도록 하는 선분만 남겨야 하니 먼저 최대 가중치의 MST를 만들고 그것을 전체에서 뺀다. 

import sys 
import heapq
input = sys.stdin.readline 
n,m = map(int, input().split())

edges =[]

ans = 0 
parent =[i for i in range(n+1)] 
def find(a):
    if a != parent[a] :
        parent[a] = find(parent[a])
    return parent[a] 

def union(a,b):
    a= find(a)
    b= find(b)
    if a<b :
        parent[b] = a 
    else :
        parent[a] = b 
con_sum = 0 
total =0 
for i in range(m):
    a,b,c,d= map(int, input().split())
    total += c
    if d == 1 :
        con_sum += c
        union(a,b)
    else:
        edges.append((c,a,b))
        
edges = sorted(edges, key = lambda x : -x[0])



cnt = 0 
ans = 0 
for cost,x,y in edges:
    if find(x) == find(y):
        continue 
    else :
        cnt += 1 
        con_sum += cost 
        union(x,y)
print(total-con_sum)