#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<ll,ll>
#define fir first
#define sec second
const int maxn=1e6;
int n,m;
vector<P> E[maxn+5];
bool vis[maxn+5];
ll dis[maxn+5];
priority_queue<P,vector<P>,greater<P>> pq;
int tot;
int dfn[maxn+5],low[maxn+5],idt;
int st[maxn+5],top;
vector<int> V[maxn+5];
map<int,ll> mp[maxn+5];
queue<int> qu;
inline void Dij(){
	int u,v;ll w;
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0,pq.push(P(0,1));
	while(pq.size()){
		u=pq.top().sec,pq.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(P t:E[u]){
			v=t.fir,w=t.sec;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				pq.push(P(dis[v],v));
			}
		}
	}
}
void Dfs(int u,int fa){
	dfn[u]=low[u]=++idt;
	int v;
	st[++top]=u;
	for(P t:E[u]){
		v=t.fir;
		if(!dfn[v]){
			Dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				tot++;
				while(true){
					V[tot].emplace_back(st[top]);
					if(st[top--]==v) break;
				}
				V[tot].emplace_back(u);
			}
		}
		else if(v!=fa) low[u]=min(low[u],dfn[v]);
	}
}
inline void Update(int u){
	if(1<u&&u<n&&1<=mp[u].size()&&mp[u].size()<=2)
		qu.push(u);
}
inline void Insert(int u,int v,ll w){
	if(mp[u].count(v)){
		if(mp[u][v]!=w)
			mp[u][v]=-1;
	}
	else mp[u][v]=w;
	mp[v][u]=w;
}
inline void Delete(int u,int v){
	mp[u].erase(v);
	mp[v].erase(u);
	Update(u),Update(v);
}
signed main(){
	freopen("P8426_90.in","r",stdin);
	int u,v,x;ll w,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%lld",&u,&v,&w);
		E[u].emplace_back(P(v,w));
		E[v].emplace_back(P(u,w));
	}
	Dij();
	E[1].emplace_back(P(n,dis[n]));
	E[n].emplace_back(P(1,dis[n]));
	for(int i=1;i<=n;i++){
		if(dfn[i]) continue;
		top=0;
		Dfs(i,0);
	}
	for(int i=1;i<=tot;i++){
		bool flg1=0,flg2=0;
		for(int j:V[i]){
			flg1|=(j==1);
			flg2|=(j==n);
		}
		if(flg1&&flg2){
			memset(vis,0,sizeof(vis));
			for(int j:V[i]) vis[j]=1;
			for(int j:V[i]){
				for(P k:E[j]){
					if(vis[k.fir]){
						Insert(j,k.fir,k.sec);
						
					}
				}
			}
			for(int j:V[i]) Update(j);
			break;
		}
	}
	while(qu.size()){
		u=qu.front(),qu.pop();
		if(mp[u].size()==1)
			Delete(u,(*mp[u].begin()).fir);
		if(mp[u].size()==2){
			v=(*mp[u].begin()).fir;
			w=(*mp[u].begin()).sec;
			x=(*mp[u].rbegin()).fir;
			y=(*mp[u].rbegin()).sec;
			if(w==-1||y==-1) Insert(v,x,-1);
			else Insert(v,x,w+y);
			Delete(u,v);
			Delete(u,x);
		}
	}
	if(mp[1].size()==1&&mp[1][n]!=-1) puts("0");
	else puts("1");
	return 0;
}