AT_soundhound2018_summer_qual_e + Graph

[problemUrl]: https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e kenkooooさんは $ n $ 頂点 $ m $ 辺の単純連結グラフを拾いました。 グラフの頂点には $ 1 $ から $ n $ の番号が付けられていて、 $ i $ 番目の辺は頂点 $ u_i $ と $ v_i $ をつないでいます。 また、$ i $ 番目の辺には整数 $ s_i $ が定められています。 kenkooooさんは次の条件を満たすようにそれぞれの頂点に *正の整数* を書き込もうとしています。 - どの辺 $ i $ についても、頂点 $ u_i $ と $ v_i $ に書かれた正の整数の和は $ s_i $ に等しい 条件を満たすような正の整数の書き方が何通りあるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ m $ $ u_1 $ $ v_1 $ $ s_1 $ $ : $ $ u_m $ $ v_m $ $ s_m $

条件を満たす正の整数の書き込み方が何通りあるか出力せよ。

### 制約 - $ 2\ \leq\ n\ \leq\ 10^5 $ - $ 1\ \leq\ m\ \leq\ 10^5 $ - $ 1\ \leq\ u_i\