#include<iostream>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int MAX_V = 10000;
const int IINF = INT_MAX;
typedef pair<int,int> ii;

map<ii,int> mp; /////////

struct Edge{ int to,cap,rev; };

vector<Edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,int cap){
  assert( mp.count(ii(from,to)) == 0 );
  mp[ii(from,to)] = (int)G[from].size();
  G[from].push_back((Edge){to,cap,(int)G[to].size()});
  G[to].push_back((Edge){from,0,(int)G[from].size()-1});
}

int dfs(int v,int t,int f){
  if( v == t ) return f;
  used[v] = true;
  for(int i=0;i<(int)G[v].size();i++){
    Edge &e = G[v][i];
    if( !used[e.to] && e.cap > 0 ){
      int d = dfs(e.to,t,min(f,e.cap));
      if( d > 0 ){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    memset(used,0,sizeof(used));
    int f = dfs(s,t,IINF);
    if( f == 0 ) return flow;
    flow += f;
  }
}

void init(int _size=MAX_V){ rep(i,_size) G[i].clear(); }

int V,E,Q;


inline void remove_edge(int u,int v){
  G[u][mp[ii(u,v)]].cap = 0;
  G[v][G[u][mp[ii(u,v)]].rev].cap = 0;
  G[v][mp[ii(v,u)]].cap = 0;
  G[u][G[v][mp[ii(v,u)]].rev].cap = 0;
}

inline bool remove(int u,int v,int source,int sink){
  Back:;
  if( G[u][mp[ii(u,v)]].cap == 1 && G[v][mp[ii(v,u)]].cap == 1 ) {
    remove_edge(u,v);
    return false;
  }

  if( G[u][mp[ii(u,v)]].cap == 0 && G[v][mp[ii(v,u)]].cap == 0 ){
    G[u][mp[ii(u,v)]].cap = 1;
    G[v][G[u][mp[ii(u,v)]].rev].cap = 0;
    G[v][mp[ii(v,u)]].cap = 1;
    G[u][G[v][mp[ii(v,u)]].rev].cap = 0;
    goto Back;
  }


  if( G[u][mp[ii(u,v)]].cap == 1 ) swap(u,v);
  memset(used,false,sizeof(used));
  int tmp = dfs(u,v,IINF);
  bool ret = false;
  if( tmp == 0 ) {
    memset(used,false,sizeof(used));
    tmp = dfs(sink,source,1);
    memset(used,false,sizeof(used));
    tmp = dfs(u,v,1);
    assert(tmp);
    ret = true;
  } 
  remove_edge(u,v);
  return ret;
}

int main(){

  set<ii> S;
  scanf("%d %d",&V,&E);
  vector<ii> es;
  rep(i,E){
    int F,T,C;
    scanf("%d %d %d",&F,&T,&C);
    add_edge(F,T,C);
    add_edge(T,F,C);
    if( F > T ) swap(F,T);
    if( C == 1 ) es.push_back(ii(F,T));
    S.insert(ii(F,T));
  }
  int source = 0, sink = V-1;
  int cur_flow = max_flow(source,sink);

  int mini = cur_flow;

  rep(_,(int)es.size()){
    //cout << "query : " << _ << " ";
    int A = es[_].first, B = es[_].second;
    if( A > B ) swap(A,B);

    bool res = remove(A,B,source,sink); //| remove(B,A,source,sink);
    if( res ) cur_flow--;
    mini = min(mini,cur_flow);
    int F = A, T = B;
    if( S.count(ii(F,T)) ) {
      int pos = IINF;
      G[A][mp[ii(A,B)]].cap = 1;
      G[B][G[A][mp[ii(A,B)]].rev].cap = 0;
      G[B][mp[ii(B,A)]].cap = 1;
      G[A][G[B][mp[ii(B,A)]].rev].cap = 0;
    } else {
      add_edge(A,B,1);
      add_edge(B,A,1);
      S.insert(ii(F,T));
    }
    memset(used,false,sizeof(used));
    cur_flow += dfs(source,sink,IINF);
  }
  if( mini <= 10000 ) {
    cout << mini << endl;
  } else {
    puts("-1");
  }
  return 0;
}

Measured memory_bytes: 4880