[SWEA] 최소 신장 트리

def Find(x):
    if P[x] != x:
        P[x] = Find(P[x])
    return P[x]

def Union(a, b):
    pa = Find(a)
    pb = Find(b)
    P[pb] = pa

T = int(input())
for TC in range(T):
    N, M = map(int, input().split())
    P = [i for i in range(N+1)]
    edges = []
    ans = 0

    for i in range(M):
        n1, n2, w = map(int, input().split())
        edges.append((w, n1, n2))

    edges.sort()
    for w, n1, n2 in edges:
        if Find(n1) == Find(n2):
            continue
        Union(n1, n2)
        ans += w

    print('#{} {}'.format(TC+1, ans))