#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> il;
typedef vector<il> vil;
vector<vil> G;
bool vis[50];
ll tw=0;
int n,m;
ll mi=1e18,ma=0;
void back(int u){
  if(u==n-1){
    mi=min(mi,tw);
    ma=max(ma,tw);
    return;
  }
  for(auto &v:G[u]){
    if(!vis[v.first]){
      vis[v.first]=1;
      tw+=v.second;
      back(v.first);
      tw-=v.second;
      vis[v.first]=0;
    }
  }
}
int main(){
   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));
  }
  vis[0]=1;
  back(0);
  cout<<(mi<ma)<<endl;
}