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
import java.util.LinkedList;
import java.util.ListIterator;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
import java.math.BigInteger;
import java.io.OutputStream;
import java.util.Vector;
import java.util.Stack;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Iterator;
import java.util.Queue;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;
import java.io.InputStream;
import java.util.Collection;
import java.io.OutputStreamWriter;
import java.io.PrintStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author ogiekako
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		MyScanner in = new MyScanner(inputStream);
		MyPrintWriter out = new MyPrintWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskB {
    public void solve(int testNumber, MyScanner in, MyPrintWriter out) {
        int n = in.nextInt(), m = in.nextInt();
        V[] vs = new V[n];
        for (int i = 0; i < n; i++) vs[i] = new V();
        E[] es = new E[m * 2];
        for (int i = 0; i < m; i++) {
            int u = in.nextInt()-1, v = in.nextInt()-1, c = in.nextInt() - 1;
            vs[u].add(es[i*2] = new E(vs[v],c));
            vs[v].add(es[i*2 + 1] = new E(vs[u],c));
            es[i*2].rev = es[i*2 + 1];
            es[i*2 + 1].rev = es[i*2];
        }
        vs[0].dfs();

        int p = 0;
        int s = p++, t = p++;
        int[] v = new int[m];
        for (int i = 0; i < m; i++)
            v[i] = p++;
        int[] c = new int[cycles.size()];
        for (int i = 0;i < cycles.size(); i++)
            c[i] = p++;

        Graph G = new Graph(p);
        for (int i = 0; i < m; i++) {
            G.addFlow(s, v[i], 1);
            if (trees.contains(i)) {
                G.addFlow(v[i], t, 1);
            }
        }
        for (int i = 0; i < c.length; i++) {
            for (int j : cycles.get(i)) {
                G.addFlow(v[j], c[i], 1);
            }
            G.addFlow(c[i], t, cycles.get(i).size() - 1);
        }

        double res = new MaxFlow(G).maxFlow(s, t);
        out.println((int)res);
    }

    List<ArrayList<Integer>> cycles = new ArrayList<>();
    HashSet<Integer> trees = new HashSet<>();

    class V extends ArrayList<E> {
        int state = 0;
        public int dfs() {
            state = 1;
            int found = -1;
            for(E e:this) {
                if (e.visited) continue;
                e.visited = true;
                e.rev.visited = true;
                if (e.to.state == 1) {
                    if (found >= 0) {
                        throw new AssertionError("" + found);
                    }
                    e.to.state = 2;
                    found = cycles.size();
                    cycles.add(new ArrayList<>());
                    cycles.get(found).add(e.c);
                } else {
                    if (e.to.state > 0) {
                        throw new AssertionError("" + e.to.state);
                    }
                    int tmp = e.to.dfs();
                    if (tmp >= 0) {
                        if (state == 2) {
                            state = 1;
                            cycles.get(tmp).add(e.c);
                        } else {
                            found = tmp;
                            cycles.get(tmp).add(e.c);
                        }
                    } else {
                        trees.add(e.c);
                    }
                }
            }
            return found;
        }
    }

    class E {
        V to;
        E rev;
        int c;
        boolean visited;

        public E(V to, int c) {
            this.to = to;
            this.c = c;
        }
    }
}

class MyScanner {
    private final InputStream in;

    public MyScanner(InputStream in) {
        this.in = in;
    }

    private static final int BUFSIZE = 65536;
    int bufLen;
    int bufPtr;
    byte[] buf = new byte[BUFSIZE];

    public int read() {
        if (bufLen == -1)
            throw new InputMismatchException();
        if (bufPtr >= bufLen) {
            bufPtr = 0;
            try {
                bufLen = in.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (bufLen <= 0)
                return -1;
        }
        return buf[bufPtr++];
    }

    public int nextInt() {
        int c = read();
        if (c == -1) throw new NoSuchElementException();
        while (c != '-' && (c < '0' || '9' < c)) {
            c = read();
            if (c == -1) throw new NoSuchElementException();
        }
        if (c == '-') return -nextInt();
        int res = 0;
        do {
            res *= 10;
            res += c - '0';
            c = read();
        } while ('0' <= c && c <= '9');
        return res;
    }

}

class MyPrintWriter {
    PrintWriter out;

    public MyPrintWriter(OutputStream outputStream) {
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public void println(int a) {
        out.println(a);
    }

    public void close() {
        out.close();
    }

}

class Graph {
    final int vertexCount;
    private EdgeList[] edges;

    public Graph(int vertexCount) {
        this.vertexCount = vertexCount;
        edges = new EdgeList[vertexCount];
        for (int i = 0; i < vertexCount; i++) edges[i] = new EdgeList();
    }

    public void addFlow(int from, int to, double capacity) {
        add(new FlowEdge(from, to, capacity));
    }

    public void add(Edge edge) {
        edges[edge.from()].add(edge);
        Edge rev = edge.reversed();
        if (rev != null) {
            edges[rev.from()].add(rev);
        }
    }

    public List<Edge> edges(int vertex) {
        return edges[vertex];
    }

    public int size() {
        return vertexCount;
    }

    public String toString() {
        StringBuilder es = new StringBuilder();
        for (int i = 0; i < vertexCount; i++) {
            if (i > 0) es.append('\n');
            es.append(edges(i));
        }
        return "Graph{" +
                "edges=" + es +
                '}';
    }

    private static class EdgeList extends ArrayList<Edge> {
        EdgeList() {
            super(0);
        }
    }
}

class MaxFlow {
    final Graph graph;
    final int n;
    int[] level, visited;
    int source, sink;
    double limit;
    EdgeIterator[] iterators;
    int flag;

    public MaxFlow(Graph graph) {
        this.graph = graph;
        n = graph.size();
    }

    public double maxFlow(int source, int sink) {
        return maxFlow(source, sink, Double.POSITIVE_INFINITY);
    }

    public double maxFlow(int _source, int _sink, double _limit) {
        source = _source;
        sink = _sink;
        limit = _limit;
        if (source == sink) return limit;
        level = new int[n];
        visited = new int[n];
        iterators = new EdgeIterator[n];
        double flow = 0;
        for (flag = 1; limit > 0; flag++) {
            setLevel(flag);
            if (visited[source] < flag) break;
            flow += blockingFlow();
        }
        return flow;
    }

    private double blockingFlow() {
        for (int i = 0; i < n; i++) iterators[i] = new EdgeIterator(graph.edges(i).listIterator());
        for (double totalFlow = 0; ; ) {
            double flow = blockingFlowDFS();
            if (flow > 1e-9) {
                totalFlow += flow;
                limit -= flow;
            } else
                return totalFlow;
        }
    }

    private double blockingFlowDFS() {
        Stack<Edge> parents = new Stack<Edge>();
        int v = source;
        for (; ; ) {
            if (v == sink) {
                double flow = limit;
                for (Edge e : parents) flow = Math.min(flow, e.residue());
                for (Edge e : parents) e.pushFlow(flow);
                return flow;
            }
            if (iterators[v].hasNext()) {
                Edge e = iterators[v].peek();
                if (e.residue() > 1e-9 && level[v] == level[e.to()] + 1) {
                    parents.push(e);
                    v = e.to();
                } else {
                    iterators[v].next();
                }
            } else {
                if (parents.isEmpty()) return 0;
                v = parents.pop().from();
                iterators[v].next();
            }
        }
    }

    private void setLevel(int flag) {
        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(sink);
        level[sink] = 0;
        visited[sink] = flag;
        while (!que.isEmpty()) {
            int u = que.poll();
            for (Edge e : graph.edges(u))
                if (e.flow() > 1e-9 && visited[e.to()] < flag) {
                    int v = e.to();
                    que.offer(v);
                    level[v] = level[u] + 1;
                    visited[v] = flag;
                }
        }
    }

    class EdgeIterator implements Iterator<Edge> {
        Iterator<Edge> iterator;
        Edge last;

        EdgeIterator(Iterator<Edge> iterator) {
            this.iterator = iterator;
        }

        public boolean hasNext() {
            return last != null || iterator.hasNext();
        }

        public Edge next() {
            if (last == null) return iterator.next();
            Edge res = last;
            last = null;
            return res;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Edge peek() {
            if (last == null) last = iterator.next();
            return last;
        }
    }

}

interface Edge {
    int from();

    int to();

    double cost();

    double residue();

    double flow();

    void pushFlow(double flow);

    Edge reversed();
}

class FlowEdge extends SimpleEdge {
    double residue;
    double flow = 0;
    Edge reversed;

    public FlowEdge(int from, int to, double capacity) {
        super(from, to);
        if (capacity < 0) throw new IllegalArgumentException(from + " " + to + " " + capacity);
        this.residue = capacity;
    }

    public double residue() {
        return residue;
    }

    public double flow() {
        return flow;
    }

    public void pushFlow(double flow) {
        if (flow > 0) {
            if (this.residue < flow)
                throw new IllegalArgumentException();
        } else {
            if (this.flow < -flow)
                throw new IllegalArgumentException();
        }
        residue -= flow;
        this.flow += flow;
    }

    public Edge reversed() {
        if (reversed == null) reversed = new ReverseEdge();
        return reversed;
    }

    public String toString() {
        return str(this);
    }

    private static String str(Edge e) {
        return String.format("%d->%d(%.2f/%.2f,%.2f)", e.from(), e.to(), e.flow(), e.flow() + e.residue(), e.cost());
    }

    private class ReverseEdge implements Edge {
        public int from() {
            return to;
        }

        public int to() {
            return from;
        }

        public double cost() {
            return -FlowEdge.this.cost();
        }

        public double residue() {
            return flow;
        }

        public double flow() {
            return residue;
        }

        public void pushFlow(double flow) {
            FlowEdge.this.pushFlow(-flow);
        }

        public Edge reversed() {
            return FlowEdge.this;
        }

        public String toString() {
            return str(this);
        }
    }
}

class SimpleEdge implements Edge {
    final int from;
    final int to;
    double cost = 1;

    public SimpleEdge(int from, int to) {
        this.from = from;
        this.to = to;
    }

    public String toString() {
        return from() + " -> " + to();
    }

    public int from() {
        return from;
    }

    public int to() {
        return to;
    }

    public double cost() {
        return cost;
    }

    public double residue() {
        return 1;
    }

    public double flow() {
        return 0;
    }

    public void pushFlow(double flow) {
        throw new UnsupportedOperationException();
    }

    public Edge reversed() {
        return null;
    }

}

