Aizuwakamatsu City is known as the "City of History". About 400 years ago, the skeleton of the castle town was created by Gamo Ujisato, but after that, it became the central city of the Aizu clan 230,000 stones, whose ancestor was Hoshina Masayuki, the half-brother of Tokugawa's third shogun Iemitsu. Developed. Many tourists from all over the country visit every year because historic sites and remnants of old days still remain throughout the city.

This year, "Shinsengumi!" Is being broadcast in the NHK Taiga drama, so the number of tourists is increasing significantly as a place related to the Shinsengumi (* 1). Therefore, the city decided to install lanterns at intervals of 100 m along the streets connecting the historic sites scattered throughout the city. The condition is that you can reach all the historic sites in the city by following the streets decorated with lanterns, but you do not have to follow it with a single stroke. However, due to the limited budget, it is necessary to minimize the number of lanterns to be installed.

Create a program that reads the data on the street connecting the historic sites and outputs the minimum number of lanterns required. However, the distance between historic sites is greater than or equal to 200 m and is given in multiples of 100. The distance from each historic site to the nearest lantern is 100 m, and there are less than 100 historic sites in the city. There is no need to install a lantern on the historic site itself.

<image>


(* 1) The Shinsengumi was established in the form of the Aizu clan's entrustment, participated in the Aizu Boshin War known for the tragedy of Byakkotai, and Toshizo Hijikata built the grave of Isami Kondo at Tenningji Temple in the city.



Input

Given multiple datasets. Each dataset is given in the following format:


n
m
a1, b1, d1
a2, b2, d2
::
am, bm, dm


The first line of each dataset is given the number of historic sites n. It is then given a few meters of streets connecting the historic sites. The following m lines are given the three comma-separated numbers ai, bi, and di. ai and bi are historic site numbers. Historic sites are numbered from 0 to n-1. ai bi indicates that there is a street connecting them, and di represents the distance of the road between ai bi.

When n is 0, it is the last input. The number of datasets does not exceed 20.

Output

For each dataset, output the minimum number of lanterns required on one line.

Example

Input

4
4
0,1,1500
0,2,2000
1,2,600
1,3,500
0


Output

23

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
from enum import Enum

class Mst(object):
	INFINITY = 999999999

	class Status(Enum):
		white = 1
		gray = 2
		black = 3

	def __init__(self, nodes, data):
		self.num_of_pathes = len(data)
		self.color = [Mst.Status.white] * nodes
		self.M = self._make_matrix(nodes, data)
		self.d = [Mst.INFINITY] * nodes
		self.p = [-1] * nodes

	def _make_matrix(self, nodes, data):
		m = [[Mst.INFINITY] * nodes for _ in range(nodes)]
		for d in data:
			m[d[0]][d[1]] = d[2]
			m[d[1]][d[0]] = d[2]
		return m

	def prim(self):
		self.d[0] = 0
		self.p[0] = -1
		while True:
			mincost = Mst.INFINITY
			for i in range(len(self.d)):
				if self.color[i] != Mst.Status.black and self.d[i] < mincost:
					mincost = self.d[i]
					u = i
			if mincost == Mst.INFINITY:
				break
			self.color[u] = Mst.Status.black
			for v in range(len(self.d)):
				if self.color[v] != Mst.Status.black and self.M[u][v] != Mst.INFINITY:
					if self.M[u][v] < self.d[v]:
						self.d[v] = self.M[u][v]
						self.p[v] = u
						self.color[v] = Mst.Status.gray
		results = []
		for i in range(len(self.p)):
			if self.p[i] != -1:
				results.append(self.M[i][self.p[i]] / 100 - 1)
		return int(sum(results))

def main(args):
	while True:
		n = int(input())
		if n == 0:
			break
		m = int(input())
		pathes = []
		for _ in range(m):
			pathes.append([int(x) for x in input().split(',')])
		s = Mst(n, pathes)
		result = s.prim()
		print(result)
main(sys.argv[1:])


while 1:
	n = int(input())
	if not n:
		break
	X = {0}
	Y = set(range(n)) - X
	s = 0
	l = [tuple(map(int, input().split(','))) for _ in range(int(input()))]
	while Y:
		cd = [i for i in l if i[0] in X and i[1] in Y or (i[0] in Y and i[1] in X)]
		cd = sorted(cd, key=lambda x: x[2])[0]
		if cd[0] in X and cd[1] in Y:
			X.add(cd[1])
			Y = Y - X
		elif cd[0] in Y and cd[1] in X:
			X.add(cd[0])
			Y = Y - X
		s += int(cd[2] / 100 - 1)
	print(s)


import array
import collections
import heapq
AdjacentVertex = collections.namedtuple('AdjacentVertex', 'vertex cost')
DIV = 100
INF = 2 ** 31 - 1

def compute_mst_prim(max_v, adj_list):
	key = collections.defaultdict(lambda : INF)
	key[0] = 0
	pq = [(key[v], v) for v in range(max_v)]
	heapq.heapify(pq)
	in_pq = array.array('B', (True for _ in range(max_v)))
	while pq:
		(_, u) = heapq.heappop(pq)
		in_pq[u] = False
		for (v, v_cost) in adj_list[u]:
			if in_pq[v]:
				w = v_cost
				if w < key[v]:
					key[v] = w
					heapq.heappush(pq, (w, v))
					in_pq[v] = True
	return key

def compute_number_of_lanterns(max_v, adj_list):
	key = compute_mst_prim(max_v, adj_list)
	return sum((x - 1 for x in key.values() if x > 0))

def main():
	while True:
		n = int(input())
		if n == 0:
			break
		m = int(input())
		adj_list = collections.defaultdict(set)
		for _ in range(m):
			(a, b, w) = map(int, input().split(','))
			adj_list[a].add((b, w // DIV))
			adj_list[b].add((a, w // DIV))
		print(compute_number_of_lanterns(n, adj_list))
main()


import sys
import os
for s in sys.stdin:
	n = int(s)
	if n == 0:
		break
	m = int(input())
	M = [[float('inf') for i in range(n)] for j in range(n)]
	for i in range(m):
		(a, b, d) = map(int, input().split(','))
		M[a][b] = d
		M[b][a] = d
	for i in range(n):
		M[i][i] = 0
	X = []
	Y = [i for i in range(n)]
	X.append(0)
	Y.remove(0)
	light_num = 0
	while len(X) != n:
		lst = []
		for x in X:
			for y in Y:
				dist = M[x][y]
				lst.append((dist, x, y))
		lst.sort()
		(dist, x, y) = lst[0]
		light_num += dist // 100 - 1
		if x not in X:
			X.append(x)
			Y.remove(x)
		else:
			X.append(y)
			Y.remove(y)
	print(light_num)


class Wood:

	def __init__(self, noods, edges):
		self.noods = noods
		self.edges = edges

	def cons(self, other):
		self.noods.extend(other.noods)
		self.edges.extend(other.edges)

class Edge:

	def __init__(self, n1, n2, length):
		self.n1 = n1
		self.n2 = n2
		self.length = length

def check(woods, edge):
	w1 = woods[edge.n1]
	w2 = woods[edge.n2]
	if w1.noods != w2.noods:
		w1.cons(w2)
		w1.edges.append(edge)
		for i in w1.noods:
			woods[i] = w1
while True:
	n = int(input())
	if n == 0:
		break
	m = int(input())
	e = []
	woods = []
	for i in range(m):
		(n1, n2, length) = map(int, input().split(','))
		edge = Edge(n1, n2, length)
		e.append(edge)
	e = sorted(e, key=lambda x: x.length)
	for i in range(n):
		wood = Wood([i], [])
		woods.append(wood)
	for edge in e:
		check(woods, edge)
	s = 0
	for edge in woods[0].edges:
		s += edge.length // 100 - 1
	print(s)


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
while 1:
	N = int(input())
	if N == 0:
		break
	(*p,) = range(N)
	M = int(input())
	E = []
	for i in range(M):
		(a, b, d) = map(int, input().split(','))
		E.append((d, a, b))
	E.sort()
	ans = 0
	for (c, a, b) in E:
		if unite(a, b):
			ans += (c - 100) // 100
	print(ans)


class Wood:

	def __init__(self, num, noods, edges):
		self.num = num
		self.noods = noods
		self.edges = edges

	def cons(self, other):
		self.noods.extend(other.noods)
		self.edges.extend(other.edges)

class Edge:

	def __init__(self, n1, n2, length):
		self.n1 = n1
		self.n2 = n2
		self.length = length

def check(woods, edge):
	if woods[edge.n1].num != woods[edge.n2].num:
		woods[edge.n1].cons(woods[edge.n2])
		woods[edge.n1].edges.append(edge)
		for i in woods[edge.n1].noods:
			woods[i] = woods[edge.n1]
while True:
	n = int(input())
	if n == 0:
		break
	m = int(input())
	e = []
	woods = []
	for i in range(m):
		(n1, n2, length) = map(int, input().split(','))
		edge = Edge(n1, n2, length)
		e.append(edge)
	e = sorted(e, key=lambda x: x.length)
	for i in range(n):
		wood = Wood(i, [i], [])
		woods.append(wood)
	for edge in e:
		check(woods, edge)
	s = 0
	for edge in woods[0].edges:
		s += edge.length // 100 - 1
	print(s)


def find(x, par_lst):
	if par_lst[x] == x:
		return x
	root = find(par_lst[x], par_lst)
	par_lst[x] = root
	return root
while True:
	n = int(input())
	if not n:
		break
	m = int(input())
	edges = []
	for _ in range(m):
		(a, b, d) = map(int, input().split(','))
		edges.append((d // 100 - 1, a, b))
	edges.sort()
	par_lst = [i for i in range(n)]
	ans = 0
	for (d, a, b) in edges:
		par_a = find(a, par_lst)
		par_b = find(b, par_lst)
		if par_a != par_b:
			par_lst[par_a] = par_b
			ans += d
	print(ans)


def kruskal(n: int, edges: list) -> int:
	tree = [-1] * n

	def get_root(x):
		if tree[x] < 0:
			return x
		tree[x] = get_root(tree[x])
		return tree[x]

	def unite(x, y):
		(x, y) = (get_root(x), get_root(y))
		if x != y:
			(big, small) = (x, y) if tree[x] < tree[y] else (y, x)
			tree[big] += tree[small]
			tree[small] = big
		return x != y
	return sum((w for ((w, _, _), _) in zip(filter(lambda p: unite(p[1], p[2]), sorted(edges)), range(n))))
while True:
	n = int(input())
	if not n:
		break
	m = int(input())
	inf = float('inf')
	edges = []
	for _ in [None] * m:
		(s, t, d) = map(int, input().split(','))
		edges.append((d // 100 - 1, s, t))
	print(kruskal(n, edges))


def kruskal(n: int, edges: list) -> int:
	tree = [-1] * n

	def get_root(x):
		if tree[x] < 0:
			return x
		else:
			tree[x] = get_root(tree[x])
			return tree[x]

	def unite(x, y):
		(x, y) = (get_root(x), get_root(y))
		if x != y:
			(big, small) = (x, y) if tree[x] < tree[y] else (y, x)
			tree[big] += tree[small]
			tree[small] = big
		return x != y
	edges.sort()
	total = 0
	cnt = 0
	for (w, s, t) in edges:
		if unite(s, t):
			cnt += 1
			total += w
			if cnt == n - 1:
				break
	return total
while True:
	n = int(input())
	if not n:
		break
	m = int(input())
	inf = float('inf')
	edges = []
	for _ in [None] * m:
		(s, t, d) = map(int, input().split(','))
		edges.append((d // 100 - 1, s, t))
	print(kruskal(n, edges))


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]
while True:
	n = int(input())
	if n == 0:
		break
	u = UnionSet(n)
	m = int(input())
	tbl = []
	for i in range(m):
		(a, b, d) = map(int, input().split(','))
		tbl.append((d // 100 - 1, a, b))
	tbl.sort()
	ans = 0
	for x in tbl:
		(d, a, b) = x
		if not u.connected(a, b):
			u.unite(a, b)
			ans += d
	print(ans)


while True:
	n = int(input())
	if n == 0:
		break
	m = int(input())
	a = [[10000 for i in range(n)] for j in range(n)]
	for i in range(m):
		(a_i, b_i, d_i) = map(int, input().split(','))
		a[a_i][b_i] = d_i // 100 - 1
		a[b_i][a_i] = d_i // 100 - 1
	w = 0
	v = set()
	v.add(0)
	while len(v) < n:
		min_w = 10000
		min_idx = 0
		i = 0
		for node in v:
			if min_w > min(a[node]):
				min_w = min(a[node])
				i = node
				min_idx = a[i].index(min_w)
		if min_idx in v:
			a[i][min_idx] = 10000
			continue
		else:
			w += min_w
			v.add(min_idx)
	print(w)


INF = 10 ** 7
while 1:
	n = int(input())
	if n == 0:
		break
	m = int(input())
	M = [[INF] * n for i in range(n)]
	for i in range(m):
		(a, b, c) = map(int, input().split(','))
		M[a][b] = c
		M[b][a] = c
	d = [INF] * n
	used = [0] * n
	d[0] = 0
	while 1:
		minv = INF
		for i in range(n):
			if not used[i] and d[i] < minv:
				minv = d[i]
				u = i
		if minv == INF:
			break
		used[u] = 1
		for i in range(n):
			if not used[i] and M[u][i] != INF and (d[i] > M[u][i]):
				d[i] = M[u][i]
	print(int(sum(d) / 100) - (n - 1))