# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
int n,cnt,dfn[100010],low[100010],ffa[100010],tot;
ll dis1[100010],dis2[100010];
bool vis[100010],good[100010];
stack<int> stk;
queue<int> que;
vector<pair<int,int>> G[100010];
map<int,bool> g[100010];
struct node
{
	int v;ll w;
	node(int _v=0,ll _w=0):v(_v),w(_w){}
	bool operator<(const node &a)const{return w>a.w;}
};
void Dij(int s,ll *dis)
{
	priority_queue<node> que;
	fill(dis+1,dis+n+1,INF);
	memset(vis+1,0,sizeof(bool)*n);
	dis[s]=0;que.emplace(s,0);
	while(!que.empty())
	{
		node t=que.top();que.pop();
		if(vis[t.v]) continue;
		int u=t.v;vis[u]=1;
		for(auto p:G[u])
		{
			int v=p.first,w=p.second;
			if(dis[v]>dis[u]+w) dis[v]=dis[u]+w,que.emplace(v,dis[v]);
		}
	}
}
void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++tot;
	stk.push(u);
	for(auto p:G[u])
	{
		int v=p.first;
		if(!dfn[v])
		{
			tarjan(v,u);low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				int w;cnt++;
				do
				{
					w=stk.top();stk.pop();
					ffa[w]=cnt;
				}while(w!=v);
				ffa[cnt]=u;
			}
		}
		else if(v!=fa) low[u]=min(low[u],dfn[v]);
	}
}
void add(int u,int v){g[u][v]=g[v][u]=1;}
void push(int u){if(u!=1 && u!=n && g[u].size()<=2) que.push(u);}
int main()
{
	int m,u,v,w;
	cin>>n>>m;cnt=n;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		G[u].emplace_back(v,w);G[v].emplace_back(u,w);
	}
	Dij(1,dis1);Dij(n,dis2);
	G[1].emplace_back(n,dis1[n]);
	G[n].emplace_back(1,dis1[n]);
	tarjan(1,0);good[1]=1;
	for(int i=2;i<=n;i++)
		if(ffa[i]==ffa[n]) good[i]=1;
	for(int u=1;u<=n;u++)if(good[u])
		for(auto p:G[u])
		{
			int v=p.first,w=p.second;
			if(!good[v] || dis1[v]+w+dis2[u]==dis1[n]) continue;
			if(dis1[u]+w+dis2[v]!=dis1[n]) return puts("1"),0;
		}
	for(int u=1;u<=n;u++)if(good[u])
		for(auto p:G[u])
		{
			int v=p.first,w=p.second;
			if(good[v] && dis1[u]+w+dis2[v]==dis1[n]) add(u,v);
		}
	for(int i=2;i<n;i++) push(i);
	while(!que.empty())
	{
		int u=que.front();que.pop();
		if(!g[u].size()) continue;
		assert(g[u].size()==2);
		vector<int> vec;
		for(auto p:g[u]) g[p.first].erase(u),vec.push_back(p.first);
		add(vec[0],vec[1]);
		push(vec[0]);push(vec[1]);
	}
	return puts(g[1].size()==1 && g[1][n]?"0":"1"),0;
}