#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}


const int INF=1001001001;

struct edge{
    int to,cap,rev;
    edge(int a,int b,int c):to(a),cap(b),rev(c){}
};

int N,E,Q;

const int MAX_V=5555;
vector<edge>G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,int cap){
    G[from].pb(edge(to,cap,G[to].size()));
    G[to].pb(edge(from,cap,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<G[v].size();i++){
        edge &e=G[v][i];
        if(used[e.to]||e.cap==0)continue;
        int d=dfs(e.to,t,min(f,e.cap));
        if(d==0)continue;
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
    }
    return 0;
}

int max_flow(int s,int t,int lim){
    int f=0;
    while(lim){
        memset(used,0,sizeof(used));
        int ff=dfs(s,t,lim);
        if(ff==0)return f;
        f+=ff;
        lim-=ff;
    }
    return f;
}


int f;
void q1(int a,int b){
    add_edge(a,b,1);
    f+=max_flow(0,N-1,INF);
}

void q2(int a,int b){
    bool f1=false,f2=false;

    for(auto &e:G[a]){
        if(e.to!=b||e.cap==0)continue;
        if(e.cap==2)f2=true,e.cap=0;
    }
    for(auto &e:G[b]){
        if(e.to!=a||e.cap==0)continue;
        if(e.cap==2)f1=true,e.cap=0;
    }
    if(!f1&&!f2)return;

    if(f2)swap(a,b);


    int tmp=max_flow(a,b,1);

    if(tmp)return;

    add_edge(0,N-1,1);
    tmp=max_flow(a,b,1);
    assert(tmp);
    G[0].pop_back();
    G[N-1].pop_back();
    f--;
}

signed main(){

    cin>>N>>E;
    vpint lis;
    rep(i,E){
        int a,b,c;
        cin>>a>>b>>c;
        if(c==1)lis.pb({a,b});
        add_edge(a,b,c);
    }

    f=max_flow(0,N-1,INF);

    int ans=f;
    rep(i,lis.size()){
        int a=lis[i].fi,b=lis[i].se;
        q2(a,b);
        chmin(ans,f);
        q1(a,b);
    }
    if(ans>10000)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}