Problem: 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

Solution (in JAVA):

Solution:
import static java.util.Arrays.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	void solve() {
		int n = sc.nextInt();
		if (n == 0) return;
		int m = sc.nextInt();
		int ans = 0;
		E[] es = new E[m];
		for (int i = 0; i < m; i++) {
			String[] ss = sc.next().split(",");
			int a = Integer.parseInt(ss[0]);
			int b = Integer.parseInt(ss[1]);
			int d = Integer.parseInt(ss[2]);
			es[i] = new E(a, b, d / 100 - 1);
		}
		sort(es);
		UnionFind uf = new UnionFind(n);
		for (E e : es) {
			if (uf.same(e.a, e.b)) {

			} else {
				uf.link(e.a,  e.b);
				ans += e.w;
			}
		}
		out.println(ans);
	}

	static class E implements Comparable<E> {
		int a;
		int b;
		int w;
		public E(int a, int b, int w) {
			this.a = a;
			this.b = b;
			this.w = w;
		}
		@Override
		public int compareTo(E o) {
			return w - o.w;
		}
	}

	public class UnionFind {
		int[] data;

		public UnionFind(int n) {
			data = new int[n];
			fill(data, -1);
		}

		boolean link(int x, int y) {
			x = root(x);
			y = root(y);
			if (x != y) {
				if (data[y] < data[x]) {
					data[y] += data[x];
					data[x] = y;
				} else {
					data[x] += data[y];
					data[y] = x;
				}
			}
			return x != y;
		}

		int root(int x) {
			return data[x] < 0 ? x : (data[x] = root(data[x]));
		}

		int size(int x) { // 要素xが含まれる集合の大きさ
			return -data[root(x)];
		}

		boolean same(int x, int y) { // 同じ集合ならtrue
			return root(x) == root(y);
		}

		int num() { // 異なる集合の数
			int res = 0;
			for (int i = 0; i < data.length; i++)
				res += (root(i) == i) ? 1 : 0;
			return res;
		}
	}




	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}