Tree is a connected undirected graph that has no cycles. Edge cactus is a connected undirected graph without loops and parallel edges, such that each edge belongs to at most one cycle.

Vasya has an edge cactus, each edge of this graph has some color.

Vasya would like to remove the minimal number of edges in such way that his cactus turned to a tree. Vasya wants to make it in such a way that there were edges of as many different colors in the resulting tree, as possible. Help him to find how many different colors can the resulting tree have.

Input

The first line contains two integers: n, m (2 ≤ n ≤ 10 000) — the number of vertices and the number of edges in Vasya's graph, respectively.

The following m lines contain three integers each: u, v, c (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ c ≤ m) — the numbers of vertices connected by the corresponding edge, and its color. It is guaranteed that the described graph is indeed an edge cactus.

Output

Output one integer: the maximal number of different colors that the resulting tree can have.

Examples

Input

4 4
1 2 4
2 3 1
3 4 2
4 2 3


Output

3


Input

7 9
1 2 1
2 3 4
3 1 5
1 4 5
4 5 2
5 1 6
1 6 4
6 7 6
7 1 3


Output

6
//package rcc2016.f;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class B2 {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";

	static void solve() {
		int n = ni(), m = ni();
		int[] from = new int[m];
		int[] to = new int[m];
		int[] color = new int[m];
		for(int i = 0;i < m;i++){
			from[i] = ni()-1;
			to[i] = ni()-1;
			color[i] = ni()-1;
		}
		boolean[] ced = new boolean[m];
		for(int i = 0;i < m;i++)ced[color[i]] = true;
		int all = 0;
		for(int i = 0;i < m;i++){
			if(ced[i])all++;
		}
		
		DJSet ds = new DJSet(n);
		boolean[] leap = new boolean[m];
		for(int i = 0;i < m;i++){
			if(ds.union(from[i], to[i])){
				leap[i] = true;
			}
		}
		
		int[] ff = new int[n-1];
		int[] tt = new int[n-1];
		int[] cc = new int[n-1];
		int p = 0;
		for(int i = 0;i < m;i++){
			if(!leap[i]){
				ff[p] = from[i];
				tt[p] = to[i];
				cc[p] = color[i];
				p++;
			}
		}
		int[][][] g = packWU(n, ff, tt, cc);
		int[][] pars = parents(g, 0);
		int[] par = pars[0], ord = pars[1], dep = pars[2], pw = pars[4];
		int[][] spar = logstepParents(par);
		
		int[][] cs = new int[m/3+3][];
		int cp = 0;
		int[] temp = new int[m+2];
		// extract cycles
		boolean[] eused = new boolean[n];
		for(int i = 0;i < m;i++){
			if(leap[i]){
				int lca = lca2(from[i], to[i], spar, dep);
				int d = dep[from[i]] + dep[to[i]] - 2*dep[lca];
				assert d >= 2;
				int lp = 0;
				temp[lp++] = color[i];
				for(int x = from[i];x != lca;x = par[x]){
					eused[x] = true;
					temp[lp++] = pw[x];
				}
				for(int x = to[i];x != lca;x = par[x]){
					eused[x] = true;
					temp[lp++] = pw[x];
				}
				assert lp == d + 1;
				cs[cp++] = Arrays.copyOf(temp, lp);
			}
		}
		
		// not-cycled edges are always not removed
		boolean[] filled = new boolean[m];
		for(int i = n-1;i >= 1;i--){
			int cur = ord[i];
			if(!eused[cur]){
				filled[pw[cur]] = true;
			}
		}
		
		// if cycle has duplicated color, it is best to remove it.
		int cq = 0;
		outer:
		for(int i = 0;i < cp;i++){
			Arrays.sort(cs[i]);
			for(int j = 0;j < cs[i].length-1;j++){
				if(cs[i][j] == cs[i][j+1]){
					for(int k = 0;k < cs[i].length;k++){
						filled[cs[i][k]] = true;
					}
					continue outer;
				}
			}
			cs[cq++] = cs[i];
		}
		
		// if two cycles have one common color, they are connected.
		// if this graph has a cycle, a cycle is connected to universe.
		int cr = cq;
		DJSet gds = new DJSet(cr+1+m);
		for(int i = 0;i < cr;i++){
			for(int j = 0;j < cs[i].length;j++){
				if(gds.union(i, cr+1+cs[i][j])){
					gds.union(i, cr);
				}
			}
		}
		// if a cycle has already-filled color, it is connected to universe.
		for(int i = 0;i < cr;i++){
			for(int v : cs[i]){
				if(filled[v]){
					gds.union(cr, i);
				}
			}
		}
		// # connected component which is not connected to universe.
		boolean[] ved = new boolean[cr+1+m];
		for(int i = 0;i < cr;i++){
			if(gds.equiv(i, cr))continue;
			int root = gds.root(i);
			if(!ved[root]){
				ved[root] = true;
				all--;
			}
		}
		out.println(all);
	}
	
	static int cross(int[] a, int[] b)
	{
		if(a.length > b.length){
			int[] c = a; a = b; b = c;
		}
		int ct = 0;
		for(int v : a){
			if(Arrays.binarySearch(b, v) >= 0)ct++;
			if(ct >= 2)return ct;
		}
		return ct;
	}
	
	static int where(int[] a, int[] b)
	{
		if(a.length > b.length){
			int[] c = a; a = b; b = c;
		}
		for(int i = 0;i < a.length;i++){
			int v = a[i];
			if(Arrays.binarySearch(b, v) >= 0)return v;
		}
		throw new RuntimeException();
	}
	
	public static int lca2(int a, int b, int[][] spar, int[] depth) {
		if (depth[a] < depth[b]) {
			b = ancestor(b, depth[b] - depth[a], spar);
		} else if (depth[a] > depth[b]) {
			a = ancestor(a, depth[a] - depth[b], spar);
		}

		if (a == b)
			return a;
		int sa = a, sb = b;
		for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
				.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
			if ((low ^ high) >= t) {
				if (spar[k][sa] != spar[k][sb]) {
					low |= t;
					sa = spar[k][sa];
					sb = spar[k][sb];
				} else {
					high = low | t - 1;
				}
			}
		}
		return spar[0][sa];
	}

	protected static int ancestor(int a, int m, int[][] spar) {
		for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
			if ((m & 1) == 1)
				a = spar[i][a];
		}
		return a;
	}

	public static int[][] logstepParents(int[] par) {
		int n = par.length;
		int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
		int[][] pars = new int[m][n];
		pars[0] = par;
		for (int j = 1; j < m; j++) {
			for (int i = 0; i < n; i++) {
				pars[j][i] = pars[j - 1][i] == -1 ? -1 : pars[j - 1][pars[j - 1][i]];
			}
		}
		return pars;
	}

	
	public static int[][] parents(int[][][] g, int root) {
		int n = g.length;
		int[] par = new int[n];
		Arrays.fill(par, -1);
		int[] dw = new int[n];
		int[] pw = new int[n];
		int[] dep = new int[n];

		int[] q = new int[n];
		q[0] = root;
		for (int p = 0, r = 1; p < r; p++) {
			int cur = q[p];
			for (int[] nex : g[cur]) {
				if (par[cur] != nex[0]) {
					q[r++] = nex[0];
					par[nex[0]] = cur;
					dep[nex[0]] = dep[cur] + 1;
					dw[nex[0]] = dw[cur] + nex[1];
					pw[nex[0]] = nex[1];
				}
			}
		}
		return new int[][] { par, q, dep, dw, pw };
	}

	
	public static class DJSet {
		public int[] upper;

		public DJSet(int n) {
			upper = new int[n];
			Arrays.fill(upper, -1);
		}

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

		public boolean equiv(int x, int y) {
			return root(x) == root(y);
		}

		public boolean union(int x, int y) {
			x = root(x);
			y = root(y);
			if (x != y) {
				if (upper[y] < upper[x]) {
					int d = x;
					x = y;
					y = d;
				}
				upper[x] += upper[y];
				upper[y] = x;
			}
			return x == y;
		}

		public int count() {
			int ct = 0;
			for (int u : upper)
				if (u < 0)
					ct++;
			return ct;
		}
	}

	
	public static int[][][] packWU(int n, int[] from, int[] to, int[] w) {
		int[][][] g = new int[n][][];
		int[] p = new int[n];
		for (int f : from)
			p[f]++;
		for (int t : to)
			p[t]++;
		for (int i = 0; i < n; i++)
			g[i] = new int[p[i]][2];
		for (int i = 0; i < from.length; i++) {
			--p[from[i]];
			g[from[i]][p[from[i]]][0] = to[i];
			g[from[i]][p[from[i]]][1] = w[i];
			--p[to[i]];
			g[to[i]][p[to[i]]][0] = from[i];
			g[to[i]][p[to[i]]][1] = w[i];
		}
		return g;
	}


	public static void main(String[] args) throws Exception {
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);

		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G - S + "ms");
	}

	private static boolean eof() {
		if (lenbuf == -1)
			return true;
		int lptr = ptrbuf;
		while (lptr < lenbuf)
			if (!isSpaceChar(inbuf[lptr++]))
				return false;

		try {
			is.mark(1000);
			while (true) {
				int b = is.read();
				if (b == -1) {
					is.reset();
					return true;
				} else if (!isSpaceChar(b)) {
					is.reset();
					return false;
				}
			}
		} catch (IOException e) {
			return true;
		}
	}

	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;

	private static int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private static boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private static int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private static double nd() {
		return Double.parseDouble(ns());
	}

	private static char nc() {
		return (char) skip();
	}

	private static String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
									// ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private static char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private static char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private static int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private static long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private static void tr(Object... o) {
		if (INPUT.length() != 0)
			System.out.println(Arrays.deepToString(o));
	}
}
