#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ll> il;
typedef vector<il> vil;
const ll MAX=1e18;
vector<vil> G;
int n,m;
ll dp[20][262145];
ll back(int u,int mask){
  if(dp[u][mask]!=-1) return dp[u][mask];
  if(u==n-1){
    return dp[u][mask]=0;
  }
  ll ans=0;
  for(auto &v:G[u]){
    if(!(mask&(1<<v.first))){
      ans=max(ans,back(v.first,mask|(1<<v.first))+v.second);
    }
  }
  return dp[u][mask]=ans;
}
ll dis[20];
void bfs(){
  for(int i=0;i<n;i++) dis[i]=MAX;
  priority_queue<ii, vector<ii>, greater<ii> > pq;
  pq.push(ii(0,0));
  dis[0]=0;
  while(!pq.empty()){
    int x=pq.top().second;
    pq.pop();
    for(auto &v:G[x]){
      if(dis[v.first]>dis[x]+v.second){
	dis[v.first]=dis[x]+v.second;
	pq.push(ii(dis[v.first],v.first));
      }
    }
  }
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  memset(dp,-1,sizeof dp);
  cin>>n>>m;
  G.resize(n+1);
  for(int i=0;i<m;i++){
    int a,b,w; cin>>a>>b>>w;
    a--; b--;
    G[a].push_back(il(b,w));
    G[b].push_back(il(a,w));
  }
  ll ma=back(0,1);
  bfs();
  cout<<(dis[n-1]<ma)<<endl;
}