#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=18;
vii E[N];
ll dp[N][1<<N], dist2[N];
int main(){
	int n, m;
	cin>>n>>m;
	for(int i=0; i<m; i++){
		int u, v, w;
		cin>>u>>v>>w;
		u--;
		v--;
		E[u].eb(v, w);
		E[v].eb(u, w);
	}
	vector<pii> dobre;
	for(int i=0; i<n; i++){
		for(int j=0; j<(1<<n); j++){
			if(j&(1<<i)){
				dobre.eb(i, j);
				dp[i][j]=-1e18;
			}
		}
	}
	dp[0][1]=0;
	ll L=0;
	for(int t=0; t<n; t++){
		for(pii i:dobre){
			int v=i.st, m=i.nd;
			for(pii u:E[v]){
				if(!((1<<u.st)&m)){
					dp[u.st][m|(1<<u.st)]=max(dp[u.st][m|(1<<u.st)], dp[v][m]+u.nd);
					if(u.st==n-1)L=max(L, dp[v][m]+u.nd);
				}
			}
		}
	}
	for(int i=0; i<n; i++){
		dist2[i]=1e18;
	}
	dist2[n-1]=0;
	priority_queue<pair<ll, int>> Q;
	for(int i=0; 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));
			}
		}
	}
	cerr<<L<<" "<<dist2[0]<<"\n";
	cout<<(L!=dist2[0]);
}