#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1LL<<60)

#define MAX_V 5000
struct edge{int to, cap, rev;};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from, int to, int cap){
    G[from].push_back(  (edge){ to  , cap, (int)G[to  ].size()   }  );
    G[to  ].push_back(  (edge){ from, 0  , (int)G[from].size()-1 }  );
}


void bfs(int s){
    rep(i,MAX_V)level[i] = -1;
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        rep(i,G[v].size()){
            edge &e = G[v][i];
            if(e.cap>0&& level[e.to]<0){
                level[e.to] = level[v]+1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f){
    if(v==t)return f;
    for(int &i = iter[v]; i<G[v].size();i++){
        edge &e = G[v][i];
        if(e.cap>0 && level[v]<level[e.to]){
            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(;;){
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while( (f=dfs(s,t,INF))>0 ){
            flow+=f;
            if(flow>100000000)return -1;
        }
    }
}

signed main(){
    int v,e;
    cin>>v>>e;
    set<pii> edges;
    rep(i,e){
        int s,t,c;
        cin>>s>>t>>c;
        if(c==1){
            edges.insert(pii(s,t));
            add_edge(s,t,4999);
            add_edge(t,s,4999);
        }
        else{
            add_edge(s,t,c*5000);
            add_edge(t,s,c*5000);
        }
    }
    
    int res = max_flow(0,v-1);
    
    if(res==-1){
        cout<<-1<<endl;
        return 0;
    }
    if(res%5000!=0)res-=5000;
    if(res>50000000) cout<<-1<<endl;
    else cout<<(res+4999)/5000<<endl;
}