#include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define ll long long

 const ll inf = 1ll << ;

 struct edge{

     int u,v,w;

 }e[];

 ll flow[];

 int op[],dis[],cnt[],a[][],pd[];

 int tot,go[],next[],first[],S,T,nodes,sz;

 int n,m,vis[],instack[],c[],top,dfn[],low[],belong[],num;

 int read(){

     int t=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void insert(int x,int y){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

 }

 void insert(int x,int y,ll z){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

     flow[tot]=z;

 }

 void add(int x,int y,ll z){

     insert(x,y,z);op[tot]=tot-;

     insert(y,x,inf);op[tot]=tot+;

 }

 void tarjan(int x){

     vis[x]=instack[x]=;

     c[++top]=x;dfn[x]=low[x]=++sz;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (!vis[pur]){

             tarjan(pur);

             low[x]=std::min(low[x],low[pur]);

         }else if (instack[pur]){

             low[x]=std::min(low[x],dfn[pur]);

         }

     }

     if (low[x]==dfn[x]){

         num++;

         while (c[top]!=x){

             belong[c[top]]=num;

             instack[c[top]]=;

             top--;

         }

             belong[c[top]]=num;

             instack[c[top]]=;

             top--;

     }

 }

 ll dfs(int x,ll f){

     if (x==T) return f;

     int mn=nodes;ll sum=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (flow[i]&&dis[pur]+==dis[x]){

             ll F=std::min(f-sum,flow[i]);

             ll save=dfs(pur,F);

             flow[i]-=save;

             flow[op[i]]+=save;

             sum+=save;

             if (dis[S]>=nodes||f==sum) return sum;

         }

         if (flow[i]) mn=std::min(mn,dis[pur]);

     }

     if (sum==){

         cnt[dis[x]]--;

         if (cnt[dis[x]]==){

             dis[S]=nodes;

         }else{

             dis[x]=mn+;

             cnt[dis[x]]++;

         }

     }

     return sum;

 }

 int main(){

     n=read();m=read();

     for (int i=;i<=m;i++){

         e[i].u=read()+,e[i].v=read()+,e[i].w=read();

         a[e[i].u][e[i].v]=;

         insert(e[i].u,e[i].v);

     }

     for (int i=;i<=n;i++)

      if (!vis[i]) tarjan(i);

     if (belong[]==belong[n]){

         puts("-1");

         return ;

     }

     for (int i=;i<=n;i++)

      a[i][i]=;

     for (int k=;k<=n;k++)

      for (int i=;i<=n;i++)

       for (int j=;j<=n;j++)

        a[i][j]|=a[i][k]&&a[k][j];

     for (int i=;i<=n;i++)

      if (a[][i]&&a[i][n]) pd[i]=;

     for (int i=;i<=m;i++)

      if (pd[e[i].u]&&pd[e[i].v])

       add(e[i].u,e[i].v,e[i].w);

     S=;T=n;nodes=n;

     int ans=;

     while (dis[S]<nodes&&ans<inf) ans+=dfs(S,inf);

     if (ans==) printf("-1");

     else printf("%d\n",ans);

 }