#include <bits/stdc++.h>
using namespace std;

#define int long long

const int inf = 1e9+7;

const int mx = 1e5+5;
vector<pair<int,int>> adj[mx]; 
vector<int> mark (mx, 0);
vector<int> d (mx, 0);
vector<int> good (mx, 0);
vector<int> sub(mx, 0);
int ans = 0;
int n, m; 
bool dfs1(int v, int p, int dd){
	d[v] = dd;
	mark [v] = 1;
	bool res = 0, res2 = (v == n-1);
	for(auto &[u, w] : adj[v]){
		if (u == p) continue;
		if(mark[u]) continue;
		res |= dfs1(u, v, dd+w); 
	}
	good[v] |= res;
	return res | res2;
}
bool dfs2(int v, int p){
	mark[v] = 1;
	bool res = 0, res2 = 0;
	for(auto &[u, w] : adj[v]){
		if (u == p) continue;
		if(mark[u]) {
			res2 |= good[u];
			continue;
		}
		res |= dfs2(u, v); 
	}
	good[v] |= res;
	return res | res2;
}
set<int>* tmp = new set<int>();
void dfs3(int v, int p, bool t){
	t |= (v == n-1);
	if(!good[v] && !t) return;
	mark[v] = 1;
	set<int>* res = new set<int>();
	for(auto &[u, w] : adj[v]){
		if (u == p) continue;
		if(mark[u]) {
			continue;
		}
		dfs3(u, v, t);
		if((*res).size() < (*tmp).size()) swap(res, tmp);
		(*res).insert((*tmp).begin(), (*tmp).end()); 
	}
	(*res).erase(d[v]);
	for(auto &[u, w] : adj[v]){
		if (u == p) continue;
		if(mark[u] && d[u] < d[v]) {
			if(good[u] && d[u]!=n-1&& abs(d[n-1]-d[u]) != abs(d[n-1]-d[v])+w) {
				ans = 1;
			}
			if((*res).size() && good[u] && *(*res).rbegin() > d[u]){
				ans = 1;
			}
		}
	}
	for(auto &[u, w] : adj[v]){
		if (u == p) continue;
		if(mark[u] && d[u] < d[v]) {
			(*res).insert(d[u]);
		}
	}
	for(auto &[u, w] : adj[v]){
		if (u == p) continue;
		if(mark[u] && d[u] < d[v]) {
			if((*res).size() && d[u] <= d[n-1] && d[v] > d[n-1] && good[u] && *(*res).begin() < d[u] && abs(d[v]-d[n-1]) != w+abs(d[u]-d[n-1])){
				ans = 1;
			}
		}
	}
	swap(tmp ,res);
}
signed main(){
	cin >> n >> m;
	for(int i = 0 ; i < m; i++){
		int u, v, w; cin >> u >> v >> w;u--;v--;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dfs1(0, 0, 0);
	mark.assign(n, 0);
	dfs2(0, 0);
	mark.assign(n, 0);
	dfs3(0, 0, 0);
	cout<<ans<<endl;

}