#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ in >> p.first >> p.second; return in; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }

struct Graph{
    struct Edge{
        int cost, from, dest;
        Edge(int cost, int dest): cost(cost), from(-1), dest(dest){ }
        Edge(int cost, int from, int dest): cost(cost), from(from), dest(dest){ }
        // bool operator == (const Edge& e) const { return cost == e.cost; }
        // bool operator < (const Edge& e) const { return cost < e.cost; }
        // bool operator == (const Edge& e) const { return from == e.from && dest == e.dest; }
        ostream& operator >> (ostream& out) const {
            return out << '(' << cost << ':' << from << ' ' << dest << ')';
        }
    };
    struct Node{
        vector<Edge> edges;
        int value;
    };
    vector<Node> nodes;
    Graph(int num): nodes(num){ }
    int id(Node* n){ return n - &nodes[0]; }
    int id(Node& n){ return &n - &nodes[0]; }
    // void print(){ for(auto& node : nodes){ prints(id(node), node.outEdges); } }
    void addEdge(int from, int dest, int cost = 1){
        nodes[from].edges.emplace_back(cost, dest);
    }
    void addEdge2(int from, int dest, int cost = 1){
        addEdge(from, dest, cost);
        addEdge(dest, from, cost);
    }
    int dfs(int idx, int v, int coef, int from = -1){
        // printde(idx, v, coef, from, nodes[idx].value);
        if(v <= 0){
            return -coef;
        }
        if(nodes[idx].value){
            return coef * (nodes[idx].value == v ? 0 : nodes[idx].value < v ? 1 : -1);
        }
        nodes[idx].value = v;
        for(auto e : nodes[idx].edges){
            if(e.cost <= v){
                return coef;
            }
            if(e.dest == from){ continue; }
            int r = dfs(e.dest, e.cost - v, coef * -1, idx);
            if(r){
                printde(r);
                return r;
            }
        }
        return 0;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    Graph g(n);
    for(int i = 0; i < m; i++){
        int u, v, s;
        cin >> u >> v >> s;
        u--; v--;
        g.addEdge2(u, v, s);
    }
    int l1 = 0, l2 = M;
    while(l1 < l2){
        // printd(l1, l2);
        for(int i = 0; i < n; i++){
            g.nodes[i].value = 0;
        }
        int piv = (l1 + l2) / 2;
        int r = g.dfs(0, piv, 1);
        // int r = g.dfs(0, piv, ?);
        if(r == 1){
            l2 = piv - 1;
        }else if(r == -1){
            l1 = piv + 1;
        }else{
            l2 = piv;
        }
    }
    printd(l1);
    for(int i = 0; i < n; i++){
        g.nodes[i].value = 0;
    }
    if(g.dfs(0, l1, 1)){
        cout << 0 << '\n';
        return 0;
    }

    int r1 = 0, r2 = M;
    while(r1 < r2){
        // printd(r1, r2);
        for(int i = 0; i < n; i++){
            g.nodes[i].value = 0;
        }
        int piv = (r1 + r2 + 1) / 2;
        int r = g.dfs(0, piv, 1);
        // int r = g.dfs(0, piv, ?);
        if(r == 1){
            r2 = piv - 1;
        }else if(r == -1){
            r1 = piv + 1;
        }else{
            r1 = piv;
        }
    }
    printd(r1);
    for(int i = 0; i < n; i++){
        g.nodes[i].value = 0;
    }
    if(g.dfs(0, r1, 1)){
        cout << 0 << '\n';
        return 0;
    }
    cout << r1 - l1 + 1 << '\n';
}


Measured memory_bytes: 9472