type
  edge=record
         l,r,w:longint;
         mark:boolean;
       end;
var
  n,m,i,j,maxtop,minlength,maxlength,minlength2,maxlength2,tot:longint;
  p:boolean;
  e:array[0..200000] of edge;
  v:array[1..20000] of longint;
  fa:array[1..20000] of longint;
  q:array[0..200002] of boolean;
  procedure sort(l,r:longint);
  var
    i,j,m:longint;
    t:edge;
  begin
    i:=l; j:=r;
    m:=e[(l+r) div 2].w;
    repeat
      while e[i].w<m do inc(i);
      while e[j].w>m do dec(j);
      if i<=j then
        begin
          t:=e[i]; e[i]:=e[j]; e[j]:=t;
          inc(i); dec(j);
        end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;
  function find(x:longint):longint;
  begin
    if x=fa[x] then exit(x)
      else fa[x]:=find(fa[x]);
    find:=fa[x];
  end;
  procedure work;
  var
    x,y,i:longint;
  begin
    minlength:=0; tot:=0;
    for i:=1 to n do
      fa[i]:=i;
    for i:=1 to m+1 do
      if not q[i] then
        begin
          x:=find(e[i].l);
          y:=find(e[i].r);
          if x<>y then
            begin
              inc(minlength,e[i].w);
              fa[x]:=y;
              inc(tot);
              if tot=n-1 then break;
            end;
        end;
    maxlength:=0; tot:=0;
    for i:=1 to n do
      fa[i]:=i;
    for i:=m+1 downto 1 do
      if not q[i] then
        begin
          x:=find(e[i].l);
          y:=find(e[i].r);
          if x<>y then
            begin
              inc(maxlength,e[i].w);
              fa[x]:=y;
              inc(tot);
              if tot=n-1 then break;
            end;
        end;
    minlength2:=0; tot:=0;
    for i:=1 to n do
      fa[i]:=i;
    for i:=0 to m+1 do
      if not q[i] then
        begin
          x:=find(e[i].l);
          y:=find(e[i].r);
          if x<>y then
            begin
              inc(minlength2,e[i].w);
              fa[x]:=y;
              inc(tot);
              if tot=n-1 then break;
            end;
        end;
    maxlength2:=0; tot:=0;
    for i:=1 to n do
      fa[i]:=i;
    for i:=m+2 downto 1 do
      if not q[i] then
        begin
          x:=find(e[i].l);
          y:=find(e[i].r);
          if x<>y then
            begin
              inc(maxlength2,e[i].w);
              fa[x]:=y;
              inc(tot);
              if tot=n-1 then break;
            end;
        end;
    if (minlength=minlength2)and(maxlength=maxlength2) then p:=true;
  end;
  procedure dfs(k,num:longint);
  var
    i:longint;
  begin
    if m+2-k<maxtop-num then exit;
    if k=m+2 then
      begin
        if num=maxtop then work;
        if p=true then
          begin
            writeln(maxtop);
            close(input); close(output);
            halt;
          end;
        exit;
      end;
    dfs(k+1,num);
    if (v[e[k].l]>1)and(v[e[k].r]>1)and(e[k].mark=false) then
      begin
        dec(v[e[k].l]);
        dec(v[e[k].r]);
        q[k]:=true;
        dfs(k+1,num+1);
        q[k]:=false;
        inc(v[e[k].l]);
        inc(v[e[k].r]);
      end;
  end;
begin
  assign(input,'mstmn.in'); reset(input);
  assign(output,'mstmn.out'); rewrite(output);
  readln(n,m);
  for i:=1 to m do
    begin
      readln(e[i].l,e[i].r,e[i].w);
      inc(v[e[i].l]);
      inc(v[e[i].r]);
    end;
  readln(e[0].l,e[0].r,e[0].w);
  inc(v[e[0].l]);
  inc(v[e[0].r]);
  e[m+1]:=e[0];
  e[m+1].mark:=true;
  sort(1,m+1);
  e[m+2]:=e[0];
  for i:=0 to m do
    begin
      maxtop:=i;
      p:=false;
      dfs(1,0);
      if p=true then
        begin
          writeln(i);
          close(input); close(output);
          halt;
        end;
    end;
end.