Problem: problem

There are $ V $ islands, numbered $ 0, 1, ..., V-1 $, respectively. There are $ E $ bridges, numbered $ 0, 1, ..., E-1 $, respectively. The $ i $ th bridge spans island $ s_i $ and island $ t_i $ and is $ c_i $ wide.

The AOR Ika-chan Corps (commonly known as the Squid Corps), which has a base on the island $ 0 $, is small in scale, so it is always being killed by the Sosu-Usa Corps (commonly known as the Sosuusa Corps) on the island $ V-1 $. .. One day, the squid group got the information that "the Sosusa group will attack tomorrow." A large number of Sosusa's subordinates move across the island from the Sosusa's base, and if even one of their subordinates reaches the Squid's base, the Squid will perish ...

Therefore, the squid group tried to avoid the crisis by putting a road closure tape on the bridge to prevent it from passing through. The length of the tape used is the sum of the widths of the closed bridges. Also, if all the subordinates of the Sosusa group always pass through a bridge with a width of $ 1 $, the squid group can ambush there to prevent them from passing through the Sosusa group.

The length of the tape it holds is $ 10 ^ 4 $. Considering the future, I would like to consume as little tape as possible. Find the minimum length of tape used to keep Sosusa's subordinates from reaching the squid's base. However, if the tape is not long enough and you are attacked by all means, output $ -1 $.



output

Output the minimum length of tape used to prevent Sosusa's subordinates from reaching the Squid's base. However, if the tape is not long enough and you are attacked by all means, output $ -1 $. Also, output a line break at the end.

Example

Input

4 4
0 1 3
0 2 4
1 3 1
2 3 5


Output

4

Solution (in CPP):

Solution:
#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;
}