#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;

static const ll INF = 1000000000;

int n,m;
#define MAX_V 5000
struct dinic{
  struct edge{int to;ll cost;int id;int revid;};
  int n;
  vector<vector<edge>> G;
  vector<ll> flow, capacity;
#define RESIDUE(id) (capacity[id]-flow[id])
  vector<int> level;
  vector<bool> finished;
  dinic(int _n){
    n = _n;
    G.assign(n,vector<edge>());
    level.assign(n,0);
    finished.assign(n,false);
  }
  void add_edge(int from,int to,ll cost){
    int id1 = flow.size();
    int id2 = flow.size()+1;
    G[from].push_back((edge){to,cost,id1,id2});
    G[to].push_back((edge){from,cost,id2,id1});
    flow.push_back(0ll);flow.push_back(0ll);
    capacity.push_back(0ll);capacity.push_back(0ll);
  }
  ll dfs(int u,int t,ll cur){
    if(u==t || cur==0)return cur;
    if(finished[u])return 0;
    finished[u] = true;
    REP(i,G[u].size()){
      edge e = G[u][i];
      if(level[e.to] > level[u]){
        ll f = dfs(e.to, t, min(cur, RESIDUE(e.id)));
        if(f>0){
          flow[e.id] += f;
          flow[e.revid] -= f;
          finished[u] = false;
          return f;
        }
      }
    }
    return 0;
  }
  ll calc(int s,int t){
    // REP(i,n)REP(j,n)flow[i][j] = capacity[i][j] = 0;
    REP(u,n)REP(j,G[u].size()){
      edge e = G[u][j];
      flow[e.id] = 0;
      capacity[e.id] += e.cost;
    }
    ll total = 0;
    while(true){
      REP(i,n)level[i] = -1;
      level[s] = 0;
      queue<int> Q; Q.push(s);
      int d = n;
      while(!Q.empty()){
        int u = Q.front(); Q.pop();
        REP(i,G[u].size()){
          edge e = G[u][i];
          if(RESIDUE(e.id)>0 && level[e.to]==-1){
            Q.push(e.to);
            level[e.to] = level[u]+1;
          }
        }
      }
      REP(i,n)finished[i] = false;
      bool flag = false;
      while(true){
        ll f = dfs(s,t,INF);
        if(f==0)break;
        total += f;
        flag = true;
      }
      if(!flag)break;
    }
    return total;
  }
};
// struct edge{
//   int s,t,cap,flow;
//   edge *rev;
// };
// vector<edge*> es[5252];
// void add_edge(int s,int t,int c){
//   edge *e1 = new edge();
//   edge *e2 = new edge();
//   e1->s = s; e1->t = t; e1->cap = c; e1->flow = 0;
//   e2->s = t; e2->t = s; e2->cap = c; e2->flow = 0;
//   e1->rev = e2;
//   e2->rev = e1;
//   es[s].push_back(e1);
//   es[t].push_back(e2);
// }

// bool used[5252];
// vector<int> dfs_path;
// bool dfs(int p, int t){
//   // printf("(p:%d, t:%d)\n",p,t);
//   used[p] = true;
//   dfs_path.push_back(p);
//   if(p==t)return true;
//   for(edge *e : es[p]){
//     edge *re = e->rev;
//     if(e->flow==e->cap)continue;
//     int to = e->t;
//     if(used[to])continue;
//     if(dfs(to,t)){
//       return true;
//     }
//   }
//   dfs_path.pop_back();
//   return false;
// }
// vector<int> get_path(int s, int t){
//   REP(i,n)used[i] = false;
//   dfs_path.clear();
//   if(!dfs(s,t))return vector<int>(1,-1);
//   return dfs_path;
// }

// int max_flow(int s, int t){
//   const int LIM = 100010001;
//   int f = 0;
//   while(true){
//     vector<int> path = get_path(s,t);
//     if(path[0] == -1)break;
//     int cap = LIM+1;
//     REP(i,path.size()-1){
//       int s = path[i];
//       int t = path[i+1];
//       for(edge *e : es[s])if(e->t == t){
//         edge *re = e->rev;
//         int c = e->cap - e->flow + re->flow;
//         // printf("%x %x %x\n",e,re,re->rev);
//         // printf("(%d,%d) : %d %d %d -> %d\n",s,t,e->cap,e->flow,re->flow,c);
//         cap = min(cap, c);
//       }
//     }
//     REP(i,path.size()-1){
//       int s = path[i];
//       int t = path[i+1];
//       for(edge *e : es[s])if(e->t == t){
//         edge *re = e->rev;
//         int tmp = cap;
//         if(re->flow > 0){
//           int minus = min(re->flow, tmp);
//           tmp -= minus;
//           re->flow -= minus;
//         }
//         e->flow += tmp;
//       }
//       // printf("%d ",s);
//     }
//     // printf("%d\n",t);
//     f += cap;
//     // printf("%d\n",cap);
//     if(f > LIM){
//       return -1;
//     }
//   }
//   return f;
// }

int main(){
  scanf("%d%d",&n,&m);
  dinic D(n);
  REP(i,m){
    int s,t,c;
    scanf("%d%d%d",&s,&t,&c);
    D.add_edge(s,t,c*10000 - (c==1 ? 1 : 0));
  }
  ll flow = D.calc(0, n-1);
  if(flow == -1){
    puts("-1");
  }else{
    flow = flow / 10000;
    if(flow > 10000){
      puts("-1");
    }else{
      printf("%lld\n",flow);
    }
  }
  // printf("%d\n", flow);
  return 0;
}



Measured memory_bytes: 3816