#include <type_traits>
#include <limits>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <list>
#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <deque>

using namespace std;


namespace SP4 {
	struct path {
		list<int> cities;
		void push(int _c) {
			cities.push_back(_c);
		}

		void pop() {
			cities.pop_back();
		}
	};

	struct solver {
		vector<int> u, v, a, b;
		vector<pair<int, int>> minDist;
		int n;
		solver(int _n, vector<int> _u, vector<int> _v, vector<int> _a, vector<int> _b)
			: n(_n), u(_u), v(_v), a(_a), b(_b), minDist(u.size())
		{

		}

		int solve(int _s, int _t, int _year) {
			list<pair<int, int>> nodes;
			nodes.push_back(make_pair(_t, 1));
			if (_t < _year)
				nodes.push_back(make_pair(_t, 0));

			while (!nodes.empty()) {

			}
		}

		int _solve(int _s, int _t, int _year) {
			
		}
	};
}

namespace SP5 {	
	struct edge {
		int val;
		int n1;
		int n2;
		bool processed = false;
	};

	struct cycle_found : public exception{
		int potentialSolution;
		cycle_found(int _potentialSolution) : potentialSolution(_potentialSolution) {}
	};

	struct node {
		int val;
		int dir = 0;
		list<edge *> edges;
	};

	struct solver {
		int minIncrease = 0;
		int maxIncrease = 2000000000;

		vector<node> & nodes;
		solver(vector<node> & _nodes) : nodes(_nodes) {

		}

		int solve() {
			try {
				nodes[0].val = 1;
				nodes[0].dir = 1;
				process(0, 1);
			}
			catch (cycle_found c) {
				if (c.potentialSolution < 1)
					return 0;

				for (auto & n : nodes) {
					n.dir = 0;
					for (auto e : n.edges) {
						e->processed = false;
					}
				}

				nodes[0].val = c.potentialSolution;
				nodes[0].dir = 1;

				return test(0) ? 1 : 0;
			}

			if (minIncrease > maxIncrease)
				return 0;

			return 1 + maxIncrease - minIncrease;
		}

		bool test(int _n) {
			for (auto e : nodes[_n].edges) {
				if (e->processed)
					continue;

				e->processed = true;
				int n2 = _n == e->n1 ? e->n2 : e->n1;

				int val = e->val - nodes[_n].val;
				if (val < 1)
					return false;

				if (nodes[n2].dir != 0 && nodes[n2].val != val)
					return false;

				nodes[n2].dir = 1;
				nodes[n2].val = val;

				if (!test(n2))
					return false;
			}

			return true;
		}

		void process(int _n, int dir) {
			for (auto e : nodes[_n].edges) {
				if (e->processed)
					continue;
				
				e->processed = true;
				int n2 = _n == e->n1 ? e->n2 : e->n1;
				
				int nextDir = dir == 1 ? 2 : 1;
				int val = e->val - nodes[_n].val;
				if (nodes[n2].dir != 0) {
					// odd cycle
					if (nodes[n2].dir != nextDir) {
						int potentialSolution = 1 + abs(nodes[n2].val - (e->val - nodes[_n].val)) / 2;
						throw cycle_found(potentialSolution);
					}

					if (nodes[n2].val != val)
						throw cycle_found(-1);
				} else {
					nodes[n2].dir = nextDir;
					nodes[n2].val = val;
					if (nextDir == 1) {
						minIncrease = max(minIncrease, 1 - nodes[n2].val);
					} else {
						if (val < 1)
							throw cycle_found(-1);

						maxIncrease = min(maxIncrease, val - 1);
					}

					process(n2, nextDir);
				}				
			}
		}
	};
}

#include <algorithm>
#include <iomanip>
#include <list>
#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <set>
#include <deque>



using namespace std;

namespace SP1 {
	bool ab(int a, int b) {
		return (a + b == 15) || (a*b == 15);
	}
}

namespace SP2 {
}

namespace SP3 {
}

namespace SP4 {
}

namespace SP5 {
}

int main()
{
	ifstream ifp("c:\\temp\\small-practice.in");
	ofstream ofp("c:\\temp\\res.out");
	istream & input = cin;
	ostream & output = cout;


	// p1
	if ( false)
	{
		int a, b;
		input >> a;
		input >> b;
		if (a + b == 15)
			output << "+";
		else if (a * b == 15)
			output << "*";
		else
			output << "x";
	}

	// p2
	if(false)
	{
		string s;
		int w;
		input >> s;
		input >> w;

		stringstream ss;
		ss << s[0];
		for (int i = 1; i < s.length(); i++) {
			if ((i % w) == 0)
				ss << s[i];
		}

		output << ss.str();
	}

	// p3
	if (false)
	{
		int m, d;
		float n;
		input >> n;
		input >> m;
		input >> d;

		float chanceOf2 = (n - (2 * d)) / n;
		if (d == 0)
			chanceOf2 = 0;
		float p = 1 / n * (1 - chanceOf2) + 1 / (n / 2) * chanceOf2;
		float res = p * (m - 1);
		output << fixed << showpoint << std::setprecision(20) << res;
	}

	// p5
	if (true)
	{
		using namespace SP5;
		int n, m;
		input >> n;
		input >> m;

		vector<node> nodes(n);
		while (m--) {
			edge * e = new edge();
			input >> e->n1 >> e->n2 >> e->val;
			e->n1--;
			e->n2--;
			nodes[e->n1].edges.push_back(e);
			nodes[e->n2].edges.push_back(e);
		}
		
		solver s(nodes);
		output << s.solve() << endl;
	}

    return 0;
}



Measured memory_bytes: 15744