/**
 * @file qoj4357-2.cpp
 * @author n685
 * @brief
 * @date 2024-06-28
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

struct DSU {
  std::vector<int> val;
  int cnt{};
  DSU() = default;
  explicit DSU(int n) : val(n, -1), cnt(n) {}
  auto find(int n) -> int { return (val[n] < 0) ? n : (val[n] = find(val[n])); }
  auto unite(int u, int v) -> bool {
    u = find(u), v = find(v);
    if (u == v) {
      return false;
    }
    if (val[u] > val[v]) {
      std::swap(u, v);
    }
    val[u] += val[v];
    val[v] = u;
    cnt--;
    return true;
  }
  auto connected(int u, int v) -> bool { return find(u) == find(v); }
  auto size(int u) -> int { return -val[find(u)]; }
  auto count() const -> int { return cnt; }
};
struct Edge {
  int a, b;
  int64_t c;
};

auto main() -> int {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int n, m;
  std::cin >> n >> m;
  std::vector<Edge> edges(m);
  std::vector<std::vector<std::pair<int, int>>> adj(n);
  for (int i = 0; i < m; ++i) {
    std::cin >> edges[i].a >> edges[i].b >> edges[i].c;
    --edges[i].a;
    --edges[i].b;
    adj[edges[i].a].emplace_back(edges[i].b, i);
    adj[edges[i].b].emplace_back(edges[i].a, i);
  }

  adj[0].emplace_back(n - 1, m);
  adj[n - 1].emplace_back(0, m);
  DSU dsu(m + 1);
  std::vector<int> num(n, -1), pe(n, -1);
  int cnt = 0;
  auto dfs = [&](auto &self, int node, int par) -> int {
    num[node] = cnt++;
    int mi = num[node];
    for (auto [i, t] : adj[node]) {
      if (t == pe[node]) {
        continue;
      }
      if (num[i] != -1) {
        if (pe[node] != -1) {
          dsu.unite(pe[node], t);
        }
        mi = std::min(mi, num[i]);
        continue;
      }
      pe[i] = t;
      mi = std::min(mi, self(self, i, node));
    }
    if (mi != num[node] and mi != num[par]) {
      dsu.unite(pe[node], pe[par]);
    }
    return mi;
  };
  dfs(dfs, 0, -1);
  std::vector<std::map<int, int64_t>> adj2(n);
  auto add = [&](int a, int b, int64_t c) {
    auto [pb, pc] = *adj2[a].try_emplace(b, c).first;
    if (pc != c) {
      std::cout << "1\n";
      std::exit(0);
    }
  };
  for (int i = 0; i < m; ++i) {
    if (dsu.connected(i, m)) {
      add(edges[i].a, edges[i].b, edges[i].c);
      add(edges[i].b, edges[i].a, edges[i].c);
    }
  }
  std::queue<int> q;
  for (int i = 1; i < n - 1; ++i) {
    if (adj2[i].size() == 2) {
      q.push(i);
    }
  }
  while (not q.empty()) {
    int node = q.front();
    q.pop();
    if (adj2[node].size() != 2) {
      continue;
    }
    auto [b1, c1] = *adj2[node].begin();
    auto [b2, c2] = *adj2[node].rbegin();
    adj2[node].clear();
    adj2[b1].erase(node);
    adj2[b2].erase(node);
    add(b1, b2, c1 + c2);
    add(b2, b1, c1 + c2);
    if (b1 != 0 and b1 != n - 1 and adj2[b1].size() == 2) {
      q.push(b1);
    }
    if (b2 != 0 and b2 != n - 1 and adj2[b2].size() == 2) {
      q.push(b2);
    }
  }
  int deg = 0;
  for (int i = 0; i < n; ++i) {
    deg += static_cast<int>(adj2[i].size());
  }
  std::cout << (deg != 2) << '\n';
}