#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = double;
const ld eps = 1e-9;
//
//using Graph = vector<vector<int>>;
//
//int dfs(const Graph&g, const int now, vector<int>&ch_cnts) {
//  ch_cnts[now]++;
//  for (auto&& e : g[now]) {
//      ch_cnts[now] += dfs(g, e, ch_cnts);
//  }
//  return ch_cnts[now];
//}
//
//struct HL_Edge {
//  int from;
//  int to;
//  bool heavy;
//};
//
//void dfs2(const Graph&g, vector<vector<HL_Edge>>&hl_tree, const int now, const vector<int>&ch_cnts) {
//
//  int max_ch_id = 1;
//  {
//      int max_ch_num = -1;
//      for (auto&&e : g[now]) {
//          if (max_ch_num < ch_cnts[e]) {
//              max_ch_num = ch_cnts[e];
//              max_ch_id = e;
//          }
//      }
//  }
//  for (auto e : g[now]) {
//      bool heavy = (e == max_ch_id);
//
//      hl_tree[now].push_back(HL_Edge{ now,e,heavy });
//  }
//  return;
//}
//
//void HL(const vector<vector<int>>&ro_tree) {
//  vector<int>ch_cnts(ro_tree.size());
//
//  dfs(ro_tree, 0, ch_cnts);
//
//  vector<vector<HL_Edge>>hl_tree(ro_tree.size());
//
//  dfs2(ro_tree, hl_tree, 0, ch_cnts);
//}
//
//namespace FastFourierTransform
//{
//  using C = complex< double >;
//
//  void DiscreteFourierTransform(vector< C > &F, bool rev)
//  {
//      const int N = (int)F.size();
//      const double PI = (rev ? -1 : 1) * acos(-1);
//      for (int i = 0, j = 1; j + 1 < N; j++) {
//          for (int k = N >> 1; k > (i ^= k); k >>= 1);
//          if (i > j) swap(F[i], F[j]);
//      }
//      C w, s, t;
//      for (int i = 1; i < N; i <<= 1) {
//          for (int k = 0; k < i; k++) {
//              w = polar(1.0, PI / i * k);
//              for (int j = 0; j < N; j += i * 2) {
//                  s = F[j + k];
//                  t = C(F[j + k + i].real() * w.real() - F[j + k + i].imag() * w.imag(),
//                      F[j + k + i].real() * w.imag() + F[j + k + i].imag() * w.real());
//                  F[j + k] = s + t, F[j + k + i] = s - t;
//              }
//          }
//      }
//      if (rev) for (int i = 0; i < N; i++) F[i] /= N;
//  }
//
//  vector< int> Multiply(const vector<int > &A, const vector<int > &B)
//  {
//      int sz = 1;
//      while (sz <= A.size() + B.size()) sz <<= 1;
//      vector< C > F(sz), G(sz);
//      for (int i = 0; i < A.size(); i++) F[i] = A[i];
//      for (int i = 0; i < B.size(); i++) G[i] = B[i];
//      DiscreteFourierTransform(F, false);
//      DiscreteFourierTransform(G, false);
//      for (int i = 0; i < sz; i++) F[i] *= G[i];
//      DiscreteFourierTransform(F, true);
//      vector< int > X(A.size() + B.size() - 1);
//      for (int i = 0; i < A.size() + B.size() - 1; i++) X[i] = F[i].real() + 0.5;
//      return (X);
//  }
//};



#define _GLIBCXX_DEBUG

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()


//const int INF = 2147483647;
//const long long int L_INF = 9223372036854775807;

typedef long long int Weight;

const Weight INF = 1e18;
const Weight ZERO = 0;
struct Edge {
	int src, dst;
	Weight weight;
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
	Edge() :src(0), dst(0), weight(0) {

	}
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;
#define RESIDUE(s,t) (capacity[s*1e4+t]-flow[s*1e4+t])

//流量0の逆辺も張らないと正しく求まらないので注意
Weight maximumFlow(const Graph &ag, int s, int t) {

	Graph g(ag);

	int n = g.size();
	//Matrix flow(n, Array(n,ZERO)), capacity(n, Array(n,ZERO));

	map<int,Weight>flow,capacity;
	REP(u, n) FOR(e, g[u]) capacity[e->src*1e4+e->dst] =capacity[1e4*e->src+e->dst]+ e->weight;


	Weight total = ZERO;
	while (1) {
		queue<int> Q; Q.push(s);
		vector<int> prev(n, -1); prev[s] = s;
		while (!Q.empty() && prev[t] < 0) {
			int u = Q.front(); Q.pop();
			FOR(e, g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > ZERO) {
				prev[e->dst] = u;
				Q.push(e->dst);
			}
		}
		if (prev[t] < 0)break; // prev[x] == -1 <=> t-side
		Weight inc = INF;
		for (int j = t; prev[j] != j; j = prev[j]){
			auto v(RESIDUE(prev[j], j));
			if (inc > v) {
				inc = v;
			}
		}
		for (int j = t; prev[j] != j; j = prev[j])
			flow[prev[j]*1e4+j] =flow[j+1e4 * prev[j]]+inc, flow[j*1e4 + prev[j]] =flow[j*1e4+prev[j]]- inc;;
		total += inc;
	}

	return total;
}


int main() {
	int V,E;cin>>V>>E;
	Graph g(V);
	for (int i = 0; i < E; ++i) {
		int f,t,c;cin>>f>>t>>c;
		long long int num=c*static_cast<long long int>(1e9);
		if(num==1e9)num--;
		g[f].push_back(Edge(f,t,num));
		g[t].push_back(Edge(t,f,num));

	}

	auto ans=maximumFlow(g,0,V-1);

	long long int nn=ans/(1e9);
	if(nn>1e4)nn=-1;
	cout<<nn<<endl;
	return 0;
}


Measured memory_bytes: 4644