Problem:


橋の取り壊し

水の国ウォーターデブンには n 個の都市があります。各都市は水に囲まれており、島国のようになっています。ウォーターデブンには m 本の橋があり、都市間の交通はそれらの橋によって行われ、全ての都市に行き来することができます。

最近、道路特定財源の見直しにより橋の維持費の削減が決定されました。全部の橋を維持することができなくなってしまい、いくつかの橋を取り壊すことになりました。そこで、ウォーターデブンはどの都市にでも行くことができるように橋を残しつつ、橋の維持費を最小化することが課題となりました。

都市の数、橋の数、各橋の維持費を入力とし、橋を利用してどの都市にも行けるようにしつつ、橋を取り壊した場合の維持費の最小値を出力するプログラムを作成してください。なお、橋の取り壊しには費用が掛からないものとします。ただし、各都市は 0 から n - 1 まで順番に番号が付けられているものとします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。

n m
a1 b1 cost1
a2 b2 cost2
:
am bm costm

１行目に都市の数 n (2 ≤ n ≤ 100)、 橋の数 m (1 ≤ m ≤ 500) が与えられます。続く m 行に第 i の橋の情報が与えられます。ai, bi は橋がつないでいる都市の番号、costi (1 ≤ costi ≤ 1000) は橋にかかる維持費を表します。

Output

データセット毎に橋の維持費の合計を１行に出力します。

Sample Input

5 6
0 2 1
2 1 3
2 3 8
1 3 2
3 4 5
1 4 4
3 3
1 2 3
2 0 3
0 1 3
0 0

Output for the Sample Input

10
6



Sample input:
5 6
0 2 1
2 1 3
2 3 8
1 3 2
3 4 5
1 4 4
3 3
1 2 3
2 0 3
0 1 3
0 0


Sample output:
10
6

Submission status: Wrong Answer

Solution code:
def f(n, ans):
    for k, c in dic.items():
        a, b = k
        if a == n:
            if not b in cost or c < cost[b]:
                cost[b] = c
    for k, c in sorted(cost.items(), key=lambda x: x[1]):
        if not k in res:
            res.append(k)
            ans += c
            del cost[k]
            return f(k, ans)
    return ans
            
while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    dic = {}
    s, b, c = map(int, raw_input().split())
    dic[(s, b)] = c
    for i in range(m-1):
        a, b, c = map(int, raw_input().split())
        dic[(a, b)] = c
    cost = {}
    res = [s]
    print f(s, 0)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


while True:
    n, m = (int(s) for s in input().split())
    if not n:
        break

    result = 0
    bridges = sorted(
        (tuple(int(s) for s in input().split()) for i in range(m)),
        key=lambda x: x[2])
    tree = UnionFind(n)

    for a, b, cost in bridges:
        if not tree.same(a, b):
            result += cost
            tree.unite(a, b)
    print(result)

Submission status: Accepted

Solution code:
par = [0]*101
rank = [0]*101
def init_union_find(V):
    for i in xrange(V):
        par[i] = i
        rank[i] = 0
        
def find(x):
    if par[x] == x: return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def unite(x,y):
    x = find(x)
    y = find(y)
    if (x == y): return
    
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if(rank[x] == rank[y]): rank[x] += 1

def same(x,y):
    return find(x) == find(y)
    
# Entry point
while 1:
    n,m = map(int,raw_input().split())
    if n == 0: break
    edge = [map(int,raw_input().split()) for i in xrange(m)]
    edge = sorted(edge, key = lambda x: x[2])
    
    init_union_find(n)
    ans = 0
    for i in xrange(m):
        e = edge[i]
        if not same(e[0],e[1]):
            unite(e[0],e[1])
            ans += e[2]
    print ans

Submission status: Accepted

Solution code:
def f(n):
    for k, c in dic.items():
        a, b = k
        if a == n:
            if not b in cost or c < cost[b]:
                cost[b] = c
        elif b == n:
            if not a in cost or c < cost[a]:
                cost[a] = c
    for k, c in sorted(cost.items(), key=lambda x: x[1]):
        if not k in res:
            res.append(k)
            ans.append(c)
            f(k)
while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    dic = {}
    s, b, c = map(int, raw_input().split())
    dic[(s, b)] = c
    for i in range(m-1):
        a, b, c = map(int, raw_input().split())
        dic[(a, b)] = c
    cost = {}
    res = [s]
    ans = []
    f(s)
    print sum(ans)

Submission status: Accepted

Solution code:
def f(n, ans):
    for k, c in dic.items():
        a, b = k
        if a == n:
            if not b in cost or c < cost[b]:
                cost[b] = c
        elif b == n:
            if not a in cost or c < cost[a]:
                cost[a] = c
    for k, c in sorted(cost.items(), key=lambda x: x[1]):
        if not k in res:
            res.append(k)
            ans += c
            del cost[k]
            return f(k, ans)
    return ans
            
while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    dic = {}
    s, b, c = map(int, raw_input().split())
    dic[(s, b)] = c
    for i in range(m-1):
        a, b, c = map(int, raw_input().split())
        dic[(a, b)] = c
    cost = {}
    res = [s]
    print f(s, 0)

Submission status: Accepted

Solution code:
def f(s, cost, route, ans):
    route.append(s)
    ans += cost[s]
    del cost[s]
    for k, c in data.items():
        a, b = k
        if s == a:
            if not b in route:
                if not b in cost or c < cost[b]:
                    cost[b] = c
        elif s == b:
            if not a in route:
                if not a in cost or c < cost[a]:
                    cost[a] = c
    if cost:
        s = sorted(cost.items(), key=lambda x: x[1])[0][0]
        return f(s, cost, route, ans)
    else:
        return ans

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(m):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    else:
        print f(0, {0:0}, [], 0)

Submission status: Accepted

Solution code:
def f(s, cost, route, ans):
    route.append(s)
    ans += cost[s]
    del cost[s]
    for k, c in data.items():
        if s in k:
            a, b = k
            b = b if s == a else a
            if not b in route:
                if not b in cost or c < cost[b]:
                    cost[b] = c
    if cost:
        s = sorted(cost.items(), key=lambda x: x[1])[0][0]
        return f(s, cost, route, ans)
    else:
        return ans

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(m):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    else:
        print f(0, {0:0}, [], 0)

Submission status: Accepted

Solution code:
def f(s, cost, route, ans):
    route.append(s)
    ans += cost[s]
    del cost[s]
    for k, c in data.items():
        if s in k:
            a, b = k
            b = b if s == a else a
            if not b in route:
                if not b in cost or c < cost[b]:
                    cost[b] = c
    if cost:
        s = sorted(cost.items(), key=lambda x: x[1])[0][0]
        return f(s, cost, route, ans)
    return ans

while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(m):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    print f(0, {0:0}, [], 0)

Submission status: Accepted

Solution code:
def f(s, cost, route, ans):
    route.append(s)
    ans += cost[s]
    del cost[s]
    for k, c in data.items():
        if s in k:
            a, b = k
            if s == a:
                if not b in route:
                    if not b in cost or c < cost[b]:
                        cost[b] = c
                        del data[(a, b)]
            elif s == b:
                if not a in route:
                    if not a in cost or c < cost[a]:
                        cost[a] = c
                        del data[(a, b)]
    if cost:
        s = sorted(cost.items(), key=lambda x: x[1])[0][0]
        return f(s, cost, route, ans)
    return ans

while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(m):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    print f(0, {0:0}, [], 0)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, size):
    self.table = [-1 for _ in xrange(size)]

  def find(self, x):
    while self.table[x] >= 0: x = self.table[x]
    return x

  def union(self, x, y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s1] >= self.table[s2]:
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
      else:
        self.table[s2] += self.table[s1]
        self.table[s1] = s2
      return True
    return False

def hash(n, s, g):
  return n*s+g

def dehash(n, hs):
  return [(hs-hs%n)/n, hs%n]

def kruskal(n, path):
  path = sorted(path.items(), key=lambda x:x[1])
  selected = {}
  union = UnionFind(n)
  for i in xrange(len(path)):
    k,v = path[i]
    s,g = dehash(n, k)
    if union.union(s, g):
      selected[k] = v
  return selected

# main
while True:
  n,m = map(int, raw_input().split())
  if n==m==0:
    break
  path = {}
  for _ in xrange(m):
    a,b,c = map(int, raw_input().split())
    path[hash(n, a, b)] = c
  result = kruskal(n, path)
  sumcost = 0
  for v in result.values():
    sumcost += v
  print sumcost

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0180

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline


class DisjointSet(object):
    def __init__(self, size):
        self.rank = []
        self.p = []
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.p.insert(x, x)
        self.rank.insert(x, 0)

    def same(self, x, y):
        return self.findSet(x) == self.findSet(y)

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


def kruskal(V, E, es):
    # V: ???????????° (0??????)
    # E: ??¨????????°
    es.sort(key=lambda x: x.c)
    uf = DisjointSet(V)
    res = 0

    for i in range(E):
        e = es[i]
        if not uf.same(e.u, e.v):
            uf.unite(e.u, e.v)
            res += e.c
    return res


edge = namedtuple('edge', ['u', 'v', 'c'])
def main(args):
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break

        es = []
        for _ in range(m):
            s, t, w = map(int, input().split())
            es.append(edge(s, t, w))

        result = kruskal(n, m, es)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# AOJ 0180 Demolition of Bridges
# Python3 2018.6.22

# UNION-FIND library
MAX = 105
id, size = [0]*MAX, [0]*MAX

def init(n):
	for i in range(n): id[i], size[i] = i, 1
	
def root(i):
	while i != id[i]:
		id[i] = id[id[i]]
		i = id[i]
	return i
	
def connected(p, q): return root(p) == root(q)
	
def unite(p, q):
	i, j = root(p), root(q)
	if i == j: return
	if size[i] < size[j]:
		id[i] = j
		size[j] += size[i]
	else:
		id[j] = i
		size[i] += size[j]
# UNION-FIND library

# 最小全域木。V:総ノード数、E:枝情報(a,b,cost)
def kruskal(V, edge):
	ee = sorted(edge, key=lambda x:(x[2]))
	init(V)
	ans = 0
	for e in ee:
		if not connected(e[0], e[1]):
			unite(e[0], e[1])
			ans += e[2]
	return ans;

while 1:
	n, m = map(int, input().split())
	if n == 0: break
	edge = []
	for i in range(m):
		s, t, w = map(int, input().split())
		edge.append((s, t, w))
	print(kruskal(n, edge))

Submission status: Accepted

Solution code:
# AOJ 0180 Demolition of Bridges
# Python3 2018.6.22

# UNION-FIND library
class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]
# UNION-FIND library

# 最小全域木。V:総ノード数、E:枝情報(a,b,cost)
def kruskal(V, edge):
	edge2 = sorted(edge, key=lambda x:(x[2]))
	u = UnionSet(V)
	ans = 0
	for e in edge2:
		if not u.connected(e[0], e[1]):
			u.unite(e[0], e[1])
			ans += e[2]
	return ans;

while 1:
	n, m = map(int, input().split())
	if n == 0: break
	edge = []
	for i in range(m):
		s, t, w = map(int, input().split())
		edge.append((s, t, w))
	print(kruskal(n, edge))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def get_par(x, par_lst):
  if x == par_lst[x]:
    return x
  p = get_par(par_lst[x], par_lst)
  par_lst[x] = p
  return p

while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  que = []
  for _ in range(m):
    a, b, c = map(int, input().split())
    heappush(que, (c, a, b))
  
  par_lst = [i for i in range(n)]
  ans = 0
  while que:
    c, a, b = heappop(que)
    pa, pb = get_par(a, par_lst), get_par(b, par_lst)
    if pa != pb:
      par_lst[pa] = pb
      ans += c
  print(ans)

Submission status: Accepted

Solution code:
INF=10000

def prim():
    mincost=[INF]*n
    used=[False]*n
    mincost[0]=0
    res=0
    while True:
        v=-1
        for u in range(n):
            if  not used[u] and (v==-1 or mincost[u]<mincost[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        res+=mincost[v]
        for u in range(n):
            mincost[u]=min(mincost[u],cost[v][u])
    return res

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    cost=[[INF]*n for i in range(n)]
    for i in range(m):
        a,b,d=map(int,raw_input().split())
        cost[a][b]=d
        cost[b][a]=d
    print prim()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
from operator import itemgetter
parent = []
rank = []

def init(n):
    global parent, rank
    parent = range(n+1)
    rank = [0] * (n + 1)
    
def find(v):
    global parent, rank
    if parent[v] == v:
        return v
    else:
        parent[v] = find(parent[v])
        return parent[v]

def union(x,y):
    global parent, rank
    xr = find(x)
    yr = find(y)
    if rank[xr] > rank[yr]:
        parent[yr] = xr
    elif rank[xr] < rank[yr]:
        parent[xr] = yr
    else:
        parent[yr] = xr
        rank[xr] += 1

def kruskal(v,e):
    visited = [False] * v
    hq = []
    t = []
    init(v)
    for a,b,c in e:
        heappush(hq,(c,(a,b)))
    while len(t) < v-1:        
        c,(a,b) = heappop(hq)
        if find(a) == find(b):
            continue
        t.append((c,(a,b)))
        union(a,b)
    return sum(map(itemgetter(0),t))

while True:
    n,m = map(int,raw_input().split())
    if n|m == 0:
        break    
    e = [map(int,raw_input().split()) for _ in xrange(m)]
    print kruskal(n,e)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        r = x
        
        while not self.par[r]<0:
            r = self.par[r]
        
        t = x
        
        while t!=r:
            tmp = t
            t = self.par[t]
            self.par[tmp] = r
        
        return r
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        
        if rx==ry:
            return
        
        if self.rank[rx]<=self.rank[ry]:
            self.par[ry] += self.par[rx]
            self.par[rx] = ry
            
            if self.rank[rx]==self.rank[ry]:
                self.rank[ry] += 1
        else:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

while True:
    n, m = map(int, input().split())
    
    if n==0 and m==0:
        exit()
        
    edges = [tuple(map(int, input().split())) for _ in range(m)]
    edges.sort(key=lambda t: t[2])
    uf = Unionfind(n)
    ans = 0
    
    for a, b, c in edges:
        if not uf.is_same(a, b):
            uf.unite(a, b)
            ans += c
    
    print(ans)

Submission status: Accepted

Solution code:

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n+1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def kr(edge,N):
    res = 0
    node = []
    G = UnionFind(N)
    for cost, p, q, in edge:
        if not G.same(p, q):
            G.union(p, q)
            res += cost
    return res

def solve():
    n,m=map(int,input().split())
    if n==0 and m==0:
        exit()
    edge=[]
    for _ in range(m):
        a,b,cost=map(int,input().split())
        edge.append((cost,a,b))
    edge.sort()
    ans=kr(edge,n)
    print(ans)
    return solve()
if __name__=="__main__":
  solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1]*n

    def find(self,x): #根を見つける、繋ぎ直す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def unite(self,x,y): #x,yの含むグループを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x,y = y,x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self,x,y):#xとyが同じグループにいるか判定
        return self.find(x) == self.find(y)

def solve(N,M):
    edges = [tuple(map(int,input().split())) for _ in range(M)]
    edges.sort(key = lambda x:x[2])
    uf = UnionFind(N)

    ans = 0
    for a,b,c in edges:
        if uf.same(a,b):
            continue
        else:
            uf.unite(a,b)
            ans += c
    print(ans)

def main():
    while True:
        N,M = map(int,input().split())
        if N == 0:
            return
        solve(N,M)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N, M = map(int, readline().split())
    if N == 0:
        return False
    *p, = range(N)
    def root(x):
        if x == p[x]:
            return x
        p[x] = y = root(p[x])
        return y
    def unite(x, y):
        px = root(x); py = root(y)
        if px == py:
            return 0
        if px < py:
            p[py] = px
        else:
            p[px] = py
        return 1

    E = []
    for i in range(M):
        a, b, c = map(int, readline().split())
        E.append((c, a, b))
    E.sort()
    ans = 0
    for c, a, b in E:
        if unite(a-1, b-1):
            ans += c
    write("%d\n" % ans)
    return True
while solve():
    ...

Submission status: Runtime Error

Solution code:
def f(n, ans):
    for k, c in dic.items():
        a, b = k
        if a == n:
            if not b in cost or c < cost[b]:
                cost[b] = c
        elif b == n:
            if not a in cost or c < cost[a]:
                cost[a] = c
    for k, c in sorted(cost.items(), key=lambda x: x[1]):
        if not k in res:
            res.append(k)
            ans += c
            del dic[k]
            return f(k, ans)
    return ans
            
while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    dic = {}
    s, b, c = map(int, raw_input().split())
    dic[(s, b)] = c
    for i in range(m-1):
        a, b, c = map(int, raw_input().split())
        dic[(a, b)] = c
    cost = {}
    res = [s]
    print f(s, 0)

Submission status: Runtime Error

Solution code:
def f(s, cost, route, ans):
    route.append(s)
    ans += cost[s]
    del cost[s]
    for k, c in data.items():
        if s in k:
            a, b = k
            b = b if s == a else a
        if not b in route:
            if not b in cost or c < cost[b]:
                cost[b] = c
    if cost:
        s = sorted(cost.items(), key=lambda x: x[1])[0][0]
        return f(s, cost, route, ans)
    else:
        return ans

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(m):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    else:
        print f(0, {0:0}, [], 0)

Submission status: Runtime Error

Solution code:
def f(s, cost, route, ans):
    route.append(s)
    ans += cost[s]
    del cost[s]
    for k, c in data.items():
            if s in k:
                a, b = k
                a, b = a, b if s == a else b, a
                if not b in route:
                    if not b in cost or c < cost[b]:
                        cost[b] = c
                        del data[(a, b)]
    if cost:
        s = sorted(cost.items(), key=lambda x: x[1])[0][0]
        return f(s, cost, route, ans)
    return ans

while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(m):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    print f(0, {0:0}, [], 0)

Submission status: Runtime Error

Solution code:
import copy

def f(s, cost, route, ans, data):
    route.append(s)
    ans += cost[s]
    del cost[s]
    _data = copy.deepcopy(data)
    for k, c in _data.items():
        if s in k:
            a, b = k
            a, b = a, b if s == a else b, a
            if not b in route:
                if not b in cost or c < cost[b]:
                    cost[b] = c
                    del data[(a, b)]
    if cost:
        s = sorted(cost.items(), key=lambda x: x[1])[0][0]
        return f(s, cost, route, ans, data)
    return ans

while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    data = {}
    for i in range(m):
        a, b, c = map(int, raw_input().split())
        data[(a, b)] = c
    print f(0, {0:0}, [], 0, data)