/*** Template Begin ***/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define REP(i, b, e) for (auto i = b; i < e; ++i)

struct Dinic {
    struct Edge {
        Edge(int to, int64_t cap, int rev) : to(to), cap(cap), rev(rev) {}

        int to, rev;
        int64_t cap;
    };

    vector<vector<Edge>> graph;
    vector<int> level;
    vector<int> iter;

    static const int64_t inf = int64_t(1) << 50;

    Dinic(int n) : graph(n), level(n), iter(n) {}

    Dinic(const vector<vector<int64_t>> &g)
        : graph(vector<vector<Edge>>(g.size())),
          level(g.size()),
          iter(g.size()) {
        for (int i = 0; i < g.size(); ++i) {
            for (int to : g[i]) {
                add_edge(i, to, 1);
            }
        }
    }

    void add_edge(int from, int to, int64_t cap) {
        graph[from].emplace_back(to, cap, (int)graph[to].size());
        graph[to].emplace_back(from, cap, (int)graph[from].size() - 1);
    }

    int64_t max_flow(int s, int t) {
        int64_t flow = 0;
        while (true) {
            bfs(s);
            if (level[t] < 0) {
                break;
            }
            fill(iter.begin(), iter.end(), 0);
            int64_t f;
            while ((f = dfs(s, t, inf)) > 0) {
                flow += f;
            }
        }

        return flow;
    }

   private:
    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);

        while (!que.empty()) {
            int v = que.front();
            que.pop();

            for (auto &e : graph[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    int64_t dfs(int v, int t, int64_t f) {
        if (v == t) return f;

        for (int &i = iter[v]; i < graph[v].size(); ++i) {
            Edge &e = graph[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                int64_t d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
};

struct Edge {
    Edge(int to, int64_t cap) : to(to), cap(cap) {}

    int to;
    int64_t cap;
};

int64_t min_cut(const vector<vector<Edge>> &graph, int s, int t) {
    Dinic dinic(graph.size());

    REP(i, 0, graph.size()) {
        for (const auto &e : graph[i]) {
            if (i < e.to) {
                dinic.add_edge(i, e.to, e.cap);
            }
        }
    }

    return dinic.max_flow(s, t);
}

int main() {
    int v, e;
    cin >> v >> e;

    const int64_t M = 100000;

    vector<vector<Edge>> graph(v);
    REP(i, 0, e) {
        int a, b, c;
        cin >> a >> b >> c;

        int m1 = -(c == 1);

        graph[a].emplace_back(b, c * M + m1);
        graph[b].emplace_back(a, c * M + m1);
    }

    int64_t f = min_cut(graph, v - 1, 0) / M;

    if (f > 10000) {
        cout << -1 << endl;
    } else {
        cout << f << endl;
    }
}

Measured memory_bytes: 3704