using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;

    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int M = cin.nextInt();
        int[] s = new int[M];
        int[] t = new int[M];
        long[] c = new long[M];

        long mul = 1000000000;

        for (int i = 0; i < M; i++)
        {
            s[i] = cin.nextInt();
            t[i] = cin.nextInt();
            c[i] = cin.nextInt() * mul;
            if (c[i] == mul) c[i]--;
        }

        V[] vs = new V[N];
        for (int i = 0; i < N; i++)
        {
            vs[i] = new V();
        }

        for (int i = 0; i < M; i++)
        {
            vs[s[i]].add(vs[t[i]], c[i]);
            vs[t[i]].add(vs[s[i]], c[i]);
        }

        long ans = dinic(vs[0], vs[N - 1]);
        ans /= mul;
        if (ans > 10000) Console.WriteLine(-1);
        else Console.WriteLine(ans);
    }

    long INF = 1L << 62;
    long dinic(V s, V t)
    {
        long flow = 0;
        for (int p = 1; ; p++)
        {
            Queue<V> que = new Queue<V>();
            s.level = 0;
            s.p = p;
            que.Enqueue(s);
            while (que.Count != 0)
            {
                V v = que.Dequeue();
                v.iter = v.es.Count - 1;
                foreach (E e in v.es)
                {
                    if (e.to.p < p && e.cap > 0)
                    {
                        e.to.level = v.level + 1;
                        e.to.p = p;
                        que.Enqueue(e.to);
                    }
                }
            }
            if (t.p < p) return flow;
            for (long f = 0; (f = dfs(s, t, INF)) > 0;)
            {
                flow += f;
            }
        }
    }

    long dfs(V v, V t, long f)
    {
        if (v == t) return f;
        for (; v.iter >= 0; v.iter--)
        {
            E e = v.es[v.iter];
            if (v.level < e.to.level && e.cap > 0)
            {
                long d = dfs(e.to, t, Math.Min(f, e.cap));
                if (d > 0)
                {
                    e.cap -= d;
                    e.rev.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    class V
    {
        public V() { }
        public List<E> es = new List<E>();
        public int level, p, iter;
        public void add(V to, long cap)
        {
            E e = new E(to, cap);
            E rev = new E(this, 0);
            e.rev = rev;
            rev.rev = e;
            es.Add(e);
            to.es.Add(rev);
        }
    }

    class E
    {
        public V to;
        public E rev;
        public long cap;
        public E(V to, long cap)
        {
            this.to = to;
            this.cap = cap;
        }

    } 
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

Measured memory_bytes: 12984