#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 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));
			}
		}
	}
	for(int i=1; i<=n; i++){
		//cerr<<i<<" "<<dist[i]<<" "<<dist2[i]<<"\n";
	}
	ll L=dist[n];
	for(int v=1; v<=n; v++){
		if(dist[v]+dist2[v]!=L){
			cerr<<v<<"\n";
			cerr<<dist[v]<<" "<<dist2[v]<<"\n";
			cout<<1;
			return 0;
		}
		for(pii u:E[v]){
			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]){
				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);
	}
	if(*(edg[1].begin())!=n){
		cout<<1;
	}
	else cout<<0;
}