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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.*;

public class B {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();

        int n = sc.nextInt();
        int m = sc.nextInt();
        MaxFlowSolver mf = new Dinic();
        Node src = mf.addNode();
        Node snk = mf.addNode();

        Map<Integer, Node> colorNodes = new HashMap<>();
        List<Integer>[] adj = new List[n];
        Map<Integer, Integer>[] edgeColors = new Map[n];
        for (int i = 0; i < n; i++) {
            edgeColors[i] = new HashMap<>();
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            int color = sc.nextInt();
            adj[u].add(v);
            adj[v].add(u);
            edgeColors[u].put(v, color);
            edgeColors[v].put(u, color);
            if (!colorNodes.containsKey(color)) {
                Node colorNode = mf.addNode();
                mf.link(colorNode, snk, 1);
                colorNodes.put(color, colorNode);
            }
        }

        BiconnectedComponentsRecursive bcc = new BiconnectedComponentsRecursive(adj);
//        System.err.println(Arrays.toString(bcc.articulation));
        int numEdgesWanted = 0;
        for (int bccId = 0; bccId < bcc.bccEdgesA.size(); bccId++) {
            List<Integer> bccA = bcc.bccEdgesA.get(bccId);
            List<Integer> bccB = bcc.bccEdgesB.get(bccId);
            int flowCapacity = bccA.size() == 1 ? 1 : bccA.size() - 1;
            Node mfNode = mf.addNode();
            mf.link(src, mfNode, flowCapacity);
            for (int edgeId = 0; edgeId < bccA.size(); edgeId++) {
                int a = bccA.get(edgeId);
                int b = bccB.get(edgeId);
                int color = edgeColors[a].get(b);
                mf.link(mfNode, colorNodes.get(color), 1);
            }
            numEdgesWanted += flowCapacity;
        }

        if (numEdgesWanted != n - 1) {
//            throw new Error("numEdgesWanted = " + numEdgesWanted);
        }

        System.out.println(mf.getMaxFlow(src, snk));
    }

    public static class BiconnectedComponentsRecursive {

        int[] low; // Lowest depth of neighbors of all descendents of v
        int[] pre; // Depth of each vertex as it's explored
        int cnt;   // Discovery time stamp
        boolean[] articulation;     // true if articulation point

        Deque<Integer> stackA;
        Deque<Integer> stackB;
        List<List<Integer>> bccEdgesA;
        List<List<Integer>> bccEdgesB;

        public BiconnectedComponentsRecursive(List<Integer>[] adj) {
            int N = adj.length;

            low = new int[N];
            pre = new int[N];
            articulation = new boolean[N];

            Arrays.fill(low, -1);
            Arrays.fill(pre, -1);

            stackA = new ArrayDeque<>();
            stackB = new ArrayDeque<>();
            bccEdgesA = new ArrayList<>();
            bccEdgesB = new ArrayList<>();

            for (int v = 0; v < N; v++) {
                if (pre[v] == -1) dfs(adj, v, v);
            }
        }

        // u is DFS parent of v
        void dfs(List<Integer>[] adj, int u, int v) {
            int children = 0;
            pre[v] = cnt++;
            low[v] = pre[v];

            for (int w : adj[v]) {
                if (pre[w] == -1) {
                    stackA.push(v);
                    stackB.push(w);

                    children++;
                    dfs(adj, v, w);

                    // Update low number
                    low[v] = Math.min(low[v], low[w]);

                    // Non-root of DFS is an articulation point
                    // if low[w] >= pre[v]
                    if (low[w] >= pre[v]) {
                        foundBcc(v, w);
                        if (u != v) {
                            articulation[v] = true;
                        }
                    }
                }
                // Update low number, ignore reverse edge leading
                // to v
                else if (w != u && pre[w] < pre[v]) {
                    stackA.push(v);
                    stackB.push(w);
                    low[v] = Math.min(low[v], pre[w]);
                }
            }

            // Root of DFS is an articulation point
            // if it has more than 1 child
            if (u == v && children > 1) {
                articulation[v] = true;
            }
        }

        // https://www.cs.umd.edu/class/fall2005/cmsc451/biconcomps.pdf
        void foundBcc(int u, int v) {
//            System.out.println("New BCC found:");
            List<Integer> edgesA = new ArrayList<>();
            List<Integer> edgesB = new ArrayList<>();
            while (!stackA.isEmpty()) {
                int a = stackA.pop();
                int b = stackB.pop();
                edgesA.add(a);
                edgesB.add(b);
//                System.out.println(a + "-" + b);
                if (a == u && b == v) {
                    break;
                }
            }
            bccEdgesA.add(edgesA);
            bccEdgesB.add(edgesB);
        }
    }

    public static class Node {
        // thou shall not create nodes except through addNode()
        private Node() { }

        List<Edge> edges = new ArrayList<Edge>();
        int index;      // index in nodes array
    }

    public static class Edge
    {
        boolean forward; // true: edge is in original graph
        // false: edge is a backward edge
        Node from, to;   // nodes connected
        int flow;        // current flow
        final int capacity;
        Edge dual;      // reference to this edge's dual
        long cost;      // only used for MinCost.

        // thou shall not create edges except through link()
        protected Edge(Node s, Node d, int c, boolean f)
        {
            forward = f;
            from = s;
            to = d;
            capacity = c;
        }

        // remaining capacity()
        int remaining() { return capacity - flow; }

        // increase flow and adjust dual
        void addFlow(int amount) {
            flow += amount;
            dual.flow -= amount;
        }
    }

    /* A Max Flow solver base class. */
    public static abstract class MaxFlowSolver {
        /* List of nodes, indexed. */
        List<Node> nodes = new ArrayList<Node>();

        /* Create an edge between nodes n1 and n2 */
        public void link(Node n1, Node n2, int capacity)
        {
            Edge e12 = new Edge(n1, n2, capacity, true);
            Edge e21 = new Edge(n2, n1, 0, false);
            e12.dual = e21;
            e21.dual = e12;
            n1.edges.add(e12);
            n2.edges.add(e21);
        }

        /* Create an edge between nodes n1 and n2 and assign cost */
        public void link(Node n1, Node n2, int capacity, long cost)
        {
            Edge e12 = new Edge(n1, n2, capacity, true);
            Edge e21 = new Edge(n2, n1, 0, false);
            e12.dual = e21;
            e21.dual = e12;
            n1.edges.add(e12);
            n2.edges.add(e21);
            e12.cost = cost;
            e21.cost = -cost;
        }

        /* Create an edge between nodes n1 and n2 */
        void link(int n1, int n2, int capacity)
        {
            link(nodes.get(n1), nodes.get(n2), capacity);
        }

        /* Create a graph with n nodes. */
        protected MaxFlowSolver(int n) {
            for (int i = 0; i < n; i++)
                addNode();
        }

        protected MaxFlowSolver() { this(0); }

        public abstract int getMaxFlow(Node src, Node snk);

        /* Add a new node. */
        public Node addNode() {
            Node n = new Node();
            n.index = nodes.size();
            nodes.add(n);
            return n;
        }
    }

    /**
     * Dinic's algorithm, Shimon Even variant.
     */
    public static class Dinic extends MaxFlowSolver
    {
        int [] dist;          // distance from src for level graph
        boolean [] blocked;   // true if all outgoing edges blocked in residual graph

        int BlockingFlow(Node src, Node snk) {
            int N = nodes.size();
            dist = new int[N];
            Arrays.fill(dist, -1);
            int [] Q = new int[N];
            int s = src.index;
            int t = snk.index;

        /* Step 1.  BFS from source to compute levels */
            dist[s] = 0;
            int head = 0, tail = 0;
            Q[tail++] = s;
            while (head < tail) {
                int x = Q[head++];
                List<Edge> succ = nodes.get(x).edges;
                for (Edge e : succ) {
                    if (dist[e.to.index] == -1 && e.remaining() > 0) {
                        dist[e.to.index] = dist[e.from.index] + 1;
                        Q[tail++] = e.to.index;
                    }
                }
            }

            if (dist[t] == -1)     // no flow if sink is not reachable
                return 0;

        /* Step 2. Push flow down until we have a blocking flow */
            int flow, totflow = 0;
            blocked = new boolean[N];
            do {
                flow = dfs(src, snk, Integer.MAX_VALUE);
                totflow += flow;
            } while (flow > 0);
            return totflow;
        }

        /*
         * Run DFS on the BFS level graph.
         */
        int dfs(Node v, Node snk, int mincap) {
            // reached sink
            if (v == snk)
                return mincap;

            for (Edge e : v.edges) {
                // standard DFS, but consider an edge only if
                if (!blocked[e.to.index]    // the path to the sink is not already blocked
                        && dist[e.from.index] + 1 == dist[e.to.index] // it's in the BFS level graph
                        && e.remaining() > 0) {  // the edge has remaining capacity
                    int flow = dfs(e.to, snk, Math.min(mincap, e.remaining()));
                    if (flow > 0) {
                        e.addFlow(flow);
                        return flow;
                    }
                }
            }
            // if we couldn't add any flow then there is no point in ever going
            // past this node again.  Mark it blocked.
            blocked[v.index] = true;
            return 0;
        }

        @Override
        public int getMaxFlow(Node src, Node snk) {
            int flow, totflow = 0;
            while ((flow = BlockingFlow(src, snk)) != 0)
                totflow += flow;
            return totflow;
        }

        public Dinic () { this(0); }
        public Dinic (int n) { super(n); }
    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
        long[] readLongArray(int n) {
            long[] a = new long[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextLong();
            }
            return a;
        }
    }
}
