解法

適当な$1$箇所を固定すれば残りがすべて定まるが、最初の$1$箇所をどうするかが問題。 そこで最初の値を$x$と置いて多項式を伝播させる (なんだか典型ぽい)。 $O(N + M)$。

頂点に多項式$f_i(x) = a_i x + b_i$を書いていく。 隣接する頂点について$g(x) := s - f(x)$として伝播させ、すでに固定された頂点同士は$f(x) + g(x) = s$であることを確認する。このとき$x$の値が一意に決定されるなら覚えておくようにする。 すべて成功したなら、すべての$f$について$f(x) \ge 1$となるような$x$の数を数えて出力。 $x$の値が未決定でない場合も確認が必要なことに注意。

二部グラフ判定をして丁寧に場合分けをしても解ける。 二分探索したさもあるが、最初の値は上限と下限の両方を持つのでたぶん無理。

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using ll = long long;
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void chmin(T & a, T const & b) { a = min(a, b); }

constexpr ll INF = (ll)1e18 + 9;
ll solve(int n, int m, vector<vector<pair<int, int> > > const & g) {
    vector<ll> a(n, INF);
    vector<ll> b(n, INF);
    ll x = INF;
    try {
        function<void (int)> dfs = [&](int i) {
            for (auto edge : g[i]) {
                int j, s; tie(j, s) = edge;
                if (a[j] == INF) {
                    // let: a_j x + b_j := s - (a_i x + b_i)
                    a[j] =   - a[i];
                    b[j] = s - b[i];
                    dfs(j);
                } else {
                    // solve: a_i x + b_i + a_j x + b_j = s
                    if (x == INF) {
                        ll num = s - b[i] - b[j];
                        ll den =     a[i] + a[j];
                        if (den == 0) {
                            if (num == 0) {
                                // nop
                            } else {
                                throw 0;
                            }
                        } else if (num % den != 0) {
                            throw 0;
                        } else {
                            x = num / den;
                        }
                    } else {
                        if ((a[i] * x + b[i]) + (a[j] * x + b[j]) != s) {
                            throw 0;
                        }
                    }
                }
            }
        };
        a[0] = 1;
        b[0] = 0;
        dfs(0);
    } catch (int) {
        return 0;
    }

    if (x != INF) {
        REP (i, n) {
            if (a[i] * x + b[i] <= 0) {
                return 0;
            }
        }
        return 1;

    } else {
        // x is arbitrary
        ll l = - INF;
        ll r = INF;
        REP (i, n) {
            // solve: a_i x + b_i > 0
            if (a[i] > 0) {
                chmax(l, (- b[i]) / a[i] + 1);
            } else if (a[i] < 0) {
                chmin(r, (- b[i]) / a[i] - 1);
            }
        }
        return max(0ll, r - l + 1);
    }
}

int main() {
    // input
    int n, m; cin >> n >> m;
    vector<vector<pair<int, int> > > g(n);
    REP (i, m) {
        int u, v, s; cin >> u >> v >> s;
        -- u; -- v;
        g[u].emplace_back(v, s);
        g[v].emplace_back(u, s);
    }

    // solve
    ll answer = solve(n, m, g);

    // output
    cout << answer << endl;
    return 0;
}