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.*;
import java.io.*;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
public class Main {
  static MaxFlow mf;
  static int source;// = 0;
  static int sink;// = gn - 1;
  static class Pair
  {
    int x, y;
    public Pair(int x, int y) {
      this.x = x;
      this.y = y;
    }
  };

  public static void main(String[] args) {
    try {
      MScanner in = new MScanner(System.in);
      BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out, "UTF-8"));
      int n = in.nextInt();
      int m = in.nextInt();
      int []color = new int[m + 1];
      int []x = new int[m + 1];
      int []y = new int[m + 1];
      int []mark = new int[m + 1];
      for (int i = 1;i <= m;++i) {
        int i1 = in.nextInt();
        int i2 = in.nextInt();
        int c = in.nextInt();
        color[i] = c;
        x[i] = i1;
        y[i] = i2;
      }

      VDCC tg = new VDCC(n, m);
      for (int i = 1;i <= m;++i) {
        tg.addEdge(x[i], y[i]);
        tg.addEdge(y[i], x[i]);
      }
      ArrayList<Integer> []circle = tg.Tarjan();
      int size = tg.size();//

      Map<Pair, Integer> emp = new TreeMap<>(new Comparator<Pair>() {
        public int compare(Pair obj1, Pair obj2) {
          if (obj1.x != obj2.x) {
            return obj1.x - obj2.x;
          }
          return obj1.y - obj2.y;
        }
        });
      for (int i = 1;i <= m;++i) {
        emp.put(new Pair(x[i], y[i]), i);
      }
      
      int gn = m * 2 + 2;
      mf = new MaxFlow(gn, 300000);
      source = 0;
      sink = gn - 1;

      for (int i = 1;i <= m;++i) {
        mf.add_edge(i + m, sink, 1);
      }
      //for (Pair pr:emp.keySet()) {
      //  System.out.println("("+pr.x + " " + pr.y + ")="+emp.get(pr));
      //}
      
      for (int i = 0;i < size;++i) {
        int sz = circle[i].size();
        if (sz == 2) continue;
        int firsteid = 0;
        Set<Integer> used = new HashSet<>();
        for (int j = 0;j < sz;++j) {
          int i1 = circle[i].get(j);
          int i2 = circle[i].get((j + 1) % sz);
          int eid = 0;
          Pair key1 = new Pair(i1, i2);
          Pair key2 = new Pair(i2, i1);
          if (emp.containsKey(key1)) {
            eid = emp.get(key1);
          } else if (emp.containsKey(key2)) {
            eid = emp.get(key2);
          } else {
            //System.out.println("can not find:"+i2 + " " + i1);
          }
          if (j == 0) firsteid = eid;
          int lc = color[eid];
          if (used.contains(lc)) continue;
          used.add(lc);
          mf.add_edge(firsteid, m + lc, 1);
          mark[eid] = 1;
        }
        mf.add_edge(source, firsteid, sz - 1);
      }
      for (int i = 1;i <= m;++i) {
        if (mark[i] == 0) {
          int lc = color[i];
          mf.add_edge(source, i, 1);
          mf.add_edge(i, m + lc, 1);
        }
      }
      
      long ans = mf.dinic(source, sink);
      System.out.println(ans);

    } catch (Exception e) {
      e.printStackTrace();
    }
  }
  static class MScanner {
    StringTokenizer st;
    BufferedReader br;
    public MScanner(InputStream system) {
      br = new BufferedReader(new InputStreamReader(system));
    }

    public MScanner(String file) throws Exception {
      br = new BufferedReader(new FileReader(file));
    }

    public String next() throws IOException {
      while (st == null || !st.hasMoreTokens())
        st = new StringTokenizer(br.readLine());
      return st.nextToken();
    }
    public int[] takearr(int n) throws IOException {
      int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
      return in;
    }
    public long[] takearrl(int n) throws IOException {
      long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
      return in;
    }
    public Integer[] takearrobj(int n) throws IOException {
      Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
      return in;
    }
    public Long[] takearrlobj(int n) throws IOException {
      Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
      return in;
    }
    public String nextLine() throws IOException {
      return br.readLine();
    }

    public int nextInt() throws IOException {
      return Integer.parseInt(next());
    }

    public double nextDouble() throws IOException {
      return Double.parseDouble(next());
    }

    public char nextChar() throws IOException {
      return next().charAt(0);
    }

    public Long nextLong() throws IOException {
      return Long.parseLong(next());
    }

    public boolean ready() throws IOException {
      return br.ready();
    }

    public void waitForInput() throws InterruptedException {
      Thread.sleep(3000);
    }
  }
}



class VDCC
{
  class Edge {
    int u, v, next;
    public Edge(int u, int v, int next) {
      this.u = u;
      this.v = v;
      this.next = next;
    }
  };
  static int MAXN = 100002;
  static Edge []e = new Edge[MAXN * 2];
  static int cnt = 1;
  static int []head = new int[MAXN];
  static int []dfn = new int[MAXN];
  static int []low = new int[MAXN];
  static int []cut = new int[MAXN];
  static int dcnt = 0;
  static int ans = 0;
  static int root = 0;
  static int n = 0;
  static int m = 0;

  static Stack<Integer> s;

  static ArrayList<Integer> []dcc = new ArrayList[MAXN];
  
  public VDCC(int n, int m)
  {
    s = new Stack<Integer>();
    for (int i = 0;i < n;++i) {
      dcc[i] = new ArrayList<Integer>();
    }
    this.n = n;
    this.m = m;
  }
  void addEdge(int u, int v)
  {
    e[cnt] = new Edge(u, v, head[u]);
    head[u] = cnt;
    cnt ++;
  }
  static void tarjan(int x) 
  {
    dfn[x] = low[x] = dcnt++;
    s.push(x);
    if (x == root && head[x] == -1) {
      dcc[ans++].add(x);
      return;
    }
    for (int i = head[x]; i > 0; i = e[i].next) {
      int y = e[i].v;
      if (dfn[y] == 0) {
        tarjan(y);
        low[x] = Math.min(low[x], low[y]);
        if (low[y] >= dfn[x]) {// x 是割点
          cut[x] = 1;
          int tmp = 0;
          do {
            tmp = s.pop();
            dcc[ans].add(tmp);
          } while (tmp != y);
          dcc[ans].add(x);
          ans++;
        }
      } else {
        low[x] = Math.min(low[x], dfn[y]);
      }
    }
  }
  static int size()
  {
    return ans;
  }
  static ArrayList<Integer> [] Tarjan()
  {
    for (int i = 1; i <= n; i++) {
      if (dfn[i] == 0) {
        root = i;
        tarjan(i);
      }
    }
    //System.out.println("ans:"+ans);
    //for (int i = 0; i < ans; i++) {
    //  System.out.println(dcc[i]);
    //}
    return dcc;
  }
};


class MaxFlow {
  public long[] flow, capa;
  public int[] from, now, level, eadj, eprev, elast;
  public int eidx, N, M;
  public static long INF = 1l << 50;

  public MaxFlow(int nodes, int edges) {
    this.N = nodes;
    this.M = edges;

    flow = new long[2*M];
    capa = new long[2*M];
    eadj = new int[2*M];
    from = new int[2*M];
    eprev = new int[2*M];
    elast = new int[N];
    level = new int[N];
    now = new int[N];
    Arrays.fill(elast, -1);
    eidx = 0;
  }

  public void add_edge(int a, int b, long c) {
    //System.out.println(a+"->"+b+":"+c);
    from[eidx] = a;eadj[eidx] = b; flow[eidx] = 0; capa[eidx] = c; eprev[eidx] = elast[a]; elast[a] = eidx++;
    from[eidx] = b;eadj[eidx] = a; flow[eidx] = c; capa[eidx] = c; eprev[eidx] = elast[b]; elast[b] = eidx++;
  }

  public long dinic(int source, int sink) {
    long res, flow = 0;
    while (bfs(source, sink)) {
      System.arraycopy(elast, 0, now, 0, N);
      while ((res = dfs(source, INF, sink)) > 0)
        flow += res;
    }
    return flow;
  }

  public boolean bfs(int source, int sink) {
    Arrays.fill(level, -1);
    int front = 0, back = 0;
    int[] queue = new int[N];

    level[source] = 0;
    queue[back++] = source;

    while (front < back && level[sink] == -1) {
      int node = queue[front++];
      for (int e = elast[node]; e != -1; e = eprev[e]) {
        int to = eadj[e];
        if (level[to] == -1 && flow[e] < capa[e]) {
          level[to] = level[node] + 1;
          queue[back++] = to;
        }
      }
    }

    return level[sink] != -1;
  }

  private long dfs(int cur, long curflow, int goal) {
    if (cur == goal) return curflow;

    for (int e = now[cur]; e != -1; now[cur] = e = eprev[e]) {
      if (level[eadj[e]] > level[cur] && flow[e] < capa[e]) {
        long res = dfs(eadj[e], Math.min(curflow, capa[e] - flow[e]), goal);
        if (res > 0) {
          flow[e] += res;
          flow[e ^ 1] -= res;
          return res;
        }
      }
    }
    return 0;
  }
}

