Problem Description

Kenkoooo found a simple connected graph with $ n $ vertices and $ m $ edges. The vertices of the graph are numbered from $ 1 $ to $ n $, and the $ i $-th edge connects vertices $ u_i $ and $ v_i $. Additionally, each edge $ i $ is assigned an integer $ s_i $.

Kenkoooo wants to write a positive integer on each vertex such that the following condition is satisfied:

• For every edge $ i $, the sum of the positive integers written on vertices $ u_i $ and $ v_i $ is equal to $ s_i $.

Determine how many ways there are to write positive integers on the vertices to satisfy the condition.

Input Format

The input is given from the standard input in the following format:

$ n $ $ m $ $ u_1 $ $ v_1 $ $ s_1 $ $ : $ $ u_m $ $ v_m $ $ s_m $

Output Format

Output the number of ways to write positive integers on the vertices to satisfy the condition.

Sample Input and Output

Sample Input #1

3 3
1 2 3
2 3 5
1 3 4

Sample Output #1

1

Sample Input #2

4 3
1 2 6
2 3 7
3 4 5

Sample Output #2

3

Sample Input #3

8 7
1 2 1000000000
2 3 2
3 4 1000000000
4 5 2
5 6 1000000000
6 7 2
7 8 1000000000

Sample Output #3

0

Notes/Hints

Constraints

• $2 \leq n \leq 10^5$
• $1 \leq m \leq 10^5$
• $1 \leq u_i < v_i \leq n$
• $2 \leq s_i \leq 10^9$
• For $i \neq j$, $u_i \neq u_j$ or $v_i \neq v_j$
• The graph is connected
• All inputs are integers

Sample Explanation 1

Writing $ 1, 2, 3 $ on vertices $ 1, 2, 3 $ respectively satisfies the condition. There are no other ways to write integers to satisfy the condition, so the answer is $ 1 $.

Sample Explanation 2

Let the numbers written on vertices $ 1, 2, 3, 4 $ be $ a, b, c, d $ respectively. The sets $ (a, b, c, d) $ that satisfy the condition are the following $ 3 $:
- $ (a, b, c, d) = (1, 5, 2, 3) $
- $ (a, b, c, d) = (2, 4, 3, 2) $
- $ (a, b, c, d) = (3, 3, 4, 1) $

见题面 Input 部分

见题面 Output 部分