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 java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class Main {
	static int V;
	static int E;
	static Edge[] es;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		
		while(true) {
			int n = sc.nextInt();
			if(n == 0) break;
			V = n;
			int m = sc.nextInt();
			E = m;
			es = new Edge[E];
			for(int i = 0; i < m; i++) {
				String[] tmp = sc.next().split(",");
				int a = Integer.parseInt(tmp[0]);
				int b = Integer.parseInt(tmp[1]);
				int c = Integer.parseInt(tmp[2]);
				
				es[i] = new Edge(a,b,c);
			}
			
			int ret = kruskal();
			
			ret -=  (n-1)*100;
			out.println(ret / 100);
		}
		out.flush();
	}
	
	public static int kruskal() {
		Arrays.sort(es,new Comp());
		init(V);
		int res = 0;
		for (int i = 0; i < E; i++) {
			Edge e = es[i];
			if(!same(e.u,e.v)) {
				unite(e.u,e.v);
				res += e.cost;
			}
		}
		return res;
	}
	
	static int[] par ;
	static int[] rank ;
	
	static void init(int n) {
		par = new int[V];
		rank = new int[V];
		for(int i = 0; i < n; i++) {
			par[i] = i;
			rank[i] = 0;
		}
	}
	
	static int find(int x) {
		if(par[x] == x) {
			return x;
		}
		else {
			return par[x] = find(par[x]);
		}
	}
	
	static void unite(int x, int 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]++;
		}
		
	}
	
	static boolean same(int x, int y) {
		return find(x) == find(y);
	}
	

}


class Edge {
	int u;
	int v;
	int cost;
	Edge(int a, int b, int c) {
		u = a;
		v = b;
		cost = c;
	}
}

class Comp implements Comparator<Edge> {

	public int compare(Edge o1, Edge o2) {
		return o1.cost - o2.cost;
	}
	
}
//------------------------------//
//-----------//
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    
    public int nextInt() {
    	return (int)nextLong();
    }
    

}