#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x; --y;
    g[x].push_back({y, z});
    g[y].push_back({x, z});
  }
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end(), [&](pair<int, int> a, pair<int, int> b) {
      return a.second > b.second;
    });
    vector<bool> was(n);
    vector<pair<int, int>> new_g;
    for (auto& p : g[i]) {
      if (!was[p.first]) {
        new_g.push_back(p);
        was[p.first] = true;
      }
    }
    g[i] = new_g;
  }
  long long L;
  const long long inf = (long long) 1e18;
  {
    vector<long long> dist(n, inf);
    dist[0] = 0;
    set<pair<long long, int>> st;
    st.emplace(0LL, 0);
    while (!st.empty()) {
      auto it = st.begin();
      int i = it->second;
      st.erase(it);
      for (auto& p : g[i]) {
        int to = p.first;
        int w = p.second;
        if (dist[to] > dist[i] + w) {
          if (dist[to] != inf) {
            st.erase({dist[to], to});
          }
          dist[to] = dist[i] + w;
          st.emplace(dist[to], to);
        }
      }
    }
    L = dist[n - 1];
  }
  vector<vector<long long>> dp(1 << n, vector<long long>(n, -inf));
  dp[1 << 0][0] = 0;
  for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
      if (!(mask >> i & 1)) {
        continue;
      }
      for (auto& p : g[i]) {
        int to = p.first;
        int w = p.second;
        if (mask >> to & 1) {
          continue;
        }
        dp[mask ^ (1 << to)][to] = max(dp[mask ^ (1 << to)][to], dp[mask][i] + w);        
      }
    }
  }
  long long mx = -inf;
  for (int mask = 0; mask < (1 << n); mask++) {
    if (mask >> (n - 1) & 1) {
      mx = max(mx, dp[mask][n - 1]);
    }
  }
  cout << (mx > L ? 1 : 0) << '\n';
  return 0;
}