#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vii = vector<pii>;
using ll = long long;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=2e5+5;
vii E[N];
ll dist[N], dist2[N];
set<int> edg[N],redg[N];
set<int> zle;
int n;
void update(int v){
	if(v>1 && v!=n && edg[v].size()==1 && redg[v].size()==1)zle.insert(v);
}
int wsk=1;
int pre[N], lo[N], kol[N], dobry[N];
void color(int v, int root){
	kol[v]=1;
	for(pii u:E[v]){
		if(u.st!=root && !kol[u.st]){
			color(u.st, root);
		}
	}
}
void dfs(int v, int par){
	pre[v]=wsk++;
	lo[v]=pre[v];
	for(pii e:E[v]){
		int u=e.st;
		if(!pre[u]){
			dfs(u, v);
		}
		if(u!=par){
			lo[v]=min(lo[v], lo[u]);
		}
	}
	if(!dobry[v] && lo[v]>=pre[par]){
		color(v, par);
	}
}
int main(){
	int m;
	cin>>n>>m;
	for(int i=0; i<m; i++){
		int u, v, w;
		cin>>u>>v>>w;
		E[u].eb(v, w);
		E[v].eb(u, w);
	}
	for(int i=1; i<=n; i++){
		dist[i]=dist2[i]=1e18;
	}
	dist[1]=0;
	dist2[n]=0;
	priority_queue<pair<ll, int>> Q;
	for(int i=1; i<=n; i++){
		Q.push(mp(-dist[i], i));
	}
	while(Q.size()){
		ll d=-Q.top().st;
		int v=Q.top().nd;
		Q.pop();
		if(dist[v]!=d)continue;
		for(pii u:E[v]){
			if(dist[u.st]>d+u.nd){
				dist[u.st]=d+u.nd;
				Q.push(mp(-dist[u.st], u.st));
			}
		}
	}
	for(int i=1; i<=n; i++){
		Q.push(mp(-dist2[i], i));
	}
	while(Q.size()){
		ll d=-Q.top().st;
		int v=Q.top().nd;
		//cerr<<d<<" "<<v<<"\n";
		Q.pop();
		if(dist2[v]!=d)continue;
		for(pii u:E[v]){
			if(dist2[u.st]>d+u.nd){
				dist2[u.st]=d+u.nd;
				Q.push(mp(-dist2[u.st], u.st));
			}
		}
	}
	ll L=dist[n];
	for(int i=1; i<=n; i++){
		dobry[i]=(dist[i]+dist2[i]==L);
		//cerr<<i<<" "<<dist[i]<<" "<<dist2[i]<<"\n";
	}
	dfs(1, 0);
	for(int v=1; v<=n; v++){
		//cerr<<v<<" "<<kol[v]<<"\n";
		if(!dobry[v] && !kol[v]){
			cerr<<v<<"\n";
			cerr<<dist[v]<<" "<<dist2[v]<<"\n";
			cout<<1;
			return 0;
		}
		if(kol[v])continue;
		for(pii u:E[v]){
			if(kol[u.st])continue;
			if(dist[u.st]>=dist[v] && dist[u.st]!=dist[v]+u.nd){
				cerr<<v<<" "<<u.st<<" "<<u.nd<<"\n";
				cout<<1;
				return 0;
			}
			else if(dist[u.st]>dist[v]){
				//cerr<<u.st<<" "<<"\n";
				edg[v].insert(u.st);
				redg[u.st].insert(v);
			}
		}
	}
	for(int i=1; i<=n; i++){
		update(i);
		//cerr<<edg[i].size()<<" "<<redg[i].size()<<"\n";
	}
	while(zle.size()){
		int v=*zle.begin();
		zle.erase(v);
		int a=*redg[v].begin(), b=*edg[v].begin();
		//cerr<<v<<" "<<a<<" "<<b<<"\n";
		edg[a].erase(v);
		redg[b].erase(v);
		edg[a].insert(b);
		redg[b].insert(a);
		update(a);
		update(b);
	}
	for(int i:edg[1]){
		//cerr<<i<<" ";
	}
	if(*(edg[1].begin())!=n){
		cout<<1;
	}
	else cout<<0;
}