#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
const ll inf=1e18;
struct E{
	int fr,to,val,id;
};
struct Node{
	ll dis;
	int x;
};
int n,m,is[400005],inq[400005],tot,low[400005],dfn[400005],sign,st[400005],top;
int sz[400005],son[400005],topp[400005],d[400005],dfnt[400005],idt[400005],fa[400005],signt;
ll dis1[400005],disn[400005];
vector<E> g[400005];
vector<int> g2[400005];
set<int> out[400005],in[400005];
bool operator < (const Node &x,const Node &y){
	return x.dis>y.dis;
}
void A2(int x,int y){
	g2[x].push_back(y);
	g2[y].push_back(x); 
}
void Tarjan(int x){
	low[x]=dfn[x]=++sign,st[++top]=x;
	for(E i:g[x]){
		int y=i.to;
		if(!dfn[y]){
			Tarjan(y),low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				tot++,A2(x,tot);
				int tmp;
				do {
					tmp=st[top--],A2(tmp,tot);
				} while(tmp!=y);
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
void dfs1(int x,int f){
	fa[x]=f,d[x]=d[f]+1,sz[x]=1;
	for(int y:g2[x]){
		if(y==f)continue;
		dfs1(y,x),sz[x]+=sz[y];
		if(sz[y]>sz[son[x]])son[x]=y;
	}
}
void dfs2(int x,int tp){
	dfnt[x]=++signt,topp[x]=tp,idt[signt]=x;
	if(son[x])dfs2(son[x],tp);
	for(int y:g2[x]){
		if(y==fa[x]||y==son[x])continue;
		dfs2(y,y);
	}
}
typedef pair<int,int> pr;
int X[400005],Y[400005];
vector<pr> Get(int x,int y){
	vector<pr> ret;
	while(topp[x]^topp[y]){
		if(d[topp[x]]<d[topp[y]])swap(x,y);
		ret.push_back({dfnt[topp[x]],dfnt[x]});
		x=fa[topp[x]];
	}
	if(dfnt[x]>dfnt[y])swap(x,y);
	ret.push_back({dfnt[x],dfnt[y]});
	return ret;
}
bool Check(int x1,int y1,int x2,int y2){
	vector<pr> s1=Get(x1,y1),s2=Get(x2,y2);
	int cnt1=0,P=0;
	for(pr i:s1){
		for(pr j:s2){
			int l=max(i.first,j.first);
			int r=min(i.second,j.second);
			if(l<=r)cnt1++,P=l;
			if(l<r)return 0;
			if(cnt1==2)return 0;
		}
	}
	if(!cnt1||idt[P]>n)return 1;
	return 0;
}
int main(){
	memset(dis1,0x3f,sizeof(dis1));
	memset(disn,0x3f,sizeof(disn));
	cin>>n>>m,tot=n;
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		g[x].push_back({x,y,z,i});
		g[y].push_back({y,x,z,i});
		X[i]=x,Y[i]=y;
	}
	priority_queue<Node> q;
	dis1[1]=0,q.push({0,1});
	while(!q.empty()){
		Node cur=q.top();
		q.pop();
		int x=cur.x;
		if(cur.dis!=dis1[x])continue;
		for(E i:g[x]){
			int y=i.to;
			if(dis1[y]>dis1[x]+i.val){
				dis1[y]=dis1[x]+i.val;
				q.push({dis1[y],y});
			}
		}
	}
	disn[n]=0,q.push({0,n});
	while(!q.empty()){
		Node cur=q.top();
		q.pop();
		int x=cur.x;
		if(cur.dis!=disn[x])continue;
		for(E i:g[x]){
			int y=i.to;
			if(disn[y]>disn[x]+i.val){
				disn[y]=disn[x]+i.val;
				q.push({disn[y],y});
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(E j:g[i]){
			if(dis1[j.to]==dis1[i]+j.val&&disn[i]==disn[j.to]+j.val){
				is[j.id]=1;
				out[i].insert(j.to);
				in[j.to].insert(i);
			}
		}
	}
	queue<int> q2;
	for(int i=1;i<=n;i++)
		if(out[i].size()==1&&in[i].size()==1)q2.push(i),inq[i]=1;
	while(!q2.empty()){
		int x=q2.front();
		q2.pop();
		int y=*in[x].begin(),z=*out[x].begin();
		//y->x->z
		in[x].erase(y),out[x].erase(z);
		out[y].erase(x),in[z].erase(x);
		out[y].insert(z),in[z].insert(y);
		if(out[y].size()==1&&in[y].size()==1&&!inq[y])q2.push(y),inq[y]=1;
		if(out[z].size()==1&&in[z].size()==1&&!inq[z])q2.push(z),inq[z]=1;
	}
	if(out[1].size()!=1||in[n].size()!=1)return puts("1"),0;
	for(int i=2;i<n;i++)if(out[i].size()||in[i].size())return puts("1"),0;
	//园方树 
	Tarjan(1);
	dfs1(1,0),dfs2(1,0);
	for(int i=1;i<=m;i++){
		if(is[i])continue;
		if(Check(1,X[i],Y[i],n))return puts("1"),0;
		if(Check(1,Y[i],X[i],n))return puts("1"),0;
	}
	puts("0");
}