#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

struct Edge {
	long long int to;
	long long int num;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;
	vector<vector<Edge>>edge(N + 1);
	for (int i = 0; i < M; i++) {
		cin >> L >> R >> K;
		edge[L].push_back({ R,K });
		edge[R].push_back({ L,K });
	}
	vector<int>dis(N + 1, MOD);
	vector < long long  int > num(N + 1, 1);
	dis[1] = 0;
	queue<int>Q;
	Q.push(1);
	while (!Q.empty()) {
		int cn = Q.front();
		Q.pop();
		for (auto i : edge[cn]) {
			if (dis[i.to] > dis[cn] + 1) {
				dis[i.to] = dis[cn] + 1;
				num[i.to] = i.num - num[cn];
				Q.push(i.to);
			}
		}
	}
	bool bin = true;
	for (int i = 1; i <= N; i++) {
		for (auto j : edge[i]) {
			if ((dis[i] & 1) == (dis[j.to] & 1))bin = false;
		}
	}
	bool made = true;
	for (int i = 1; i <= N; i++) {
		for (auto j : edge[i]) {
			if ((dis[i] & 1) != (dis[j.to] & 1)) {
				if (num[i] + num[j.to] != j.num)made = false;
			}
		}
	}
	long long int oddmin = MOD*MOD;
	long long int evenmin = MOD*MOD;
	for (int i = 1; i <= N; i++) {
		if (dis[i] & 1)oddmin = min(oddmin, num[i]);
		else evenmin = min(evenmin, num[i]);
	}
	long long int ans = 0;
	if (bin) {
		if(made)ans = max(ans, oddmin + evenmin - 1);
	}
	else {
		set<long long int>oddadd;
		set<long long int>evenadd;
		bool oddedge = false;
		bool evenedge = false;
		for (int i = 1; i <= N; i++) {
			for (auto j : edge[i]) {
				if ((dis[i] & 1) && (dis[j.to] & 1)) {
					oddedge = true;
					if (j.num - num[i] - num[j.to]) oddadd.insert({ j.num - num[i] - num[j.to] });
				}
				if (!(dis[i] & 1) && !(dis[j.to] & 1)) {
					evenedge = true;
					if (j.num - num[i] - num[j.to]) evenadd.insert({ j.num - num[i] - num[j.to] });
				}
			}
		}
		if (oddadd.size() > 1)made = false;
		if (evenadd.size() > 1)made = false;
		if (made) {
			if (oddedge&&evenedge) {
				if (oddadd.empty() && evenadd.empty() && oddmin > 0 && evenmin > 0)ans = 1;
				else if (oddadd.empty() || evenadd.empty()) {
					ans = 0;
				}
				else if (*oddadd.begin() == *evenadd.begin()*-1) {
					if (*oddadd.begin() % 2 == 0) {
						if (oddmin + *oddadd.begin() / 2 > 0 && evenmin + *evenadd.begin() / 2 > 0) {
							ans = 1;
						}
					}
				}
			}
			else if(oddedge) {
				if (oddadd.size() == 1) {
					if (*oddadd.begin() % 2 == 0) {
						if (oddmin + *oddadd.begin() / 2 > 0 && evenmin - *oddadd.begin() / 2 > 0) {
							ans = 1;
						}
					}
				}
				else {
					if (oddmin > 0 && evenmin > 0)ans = 1;
				}
			}
			else if (evenedge) {
				if (evenadd.size() == 1) {
					if (*evenadd.begin() % 2==0) {
						if (oddmin - *evenadd.begin() / 2 > 0 && evenmin + *evenadd.begin() / 2 > 0) {
							ans = 1;
						}
					}
				}
				else {
					if (oddmin > 0 && evenmin > 0)ans = 1;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9216