#P18398. Many Many Cycles

Many Many Cycles

Many Many Cycles

给定一个无向图 GG,求最大的正整数 dd,使得图中所有简单环的长度都能被 dd 整除。如果不存在这样的最大整数,输出 0。

环的长度是其中各条边长度之和。简单环不重复经过顶点,除了首尾是同一个顶点。

输入格式

第一行包含两个整数 n,mn,m,分别表示顶点数和边数:

1≤n≤5000,0≤m≤10000.1\le n\le5000,\qquad0\le m\le10000.

接下来 mm 行,每行包含三个整数 a,b,ca,b,c,表示顶点 a,ba,b 之间有一条长度为 cc 的无向边:

1≤a,b≤n,1≤c≤109.1\le a,b\le n,\qquad1\le c\le10^9.

保证图中没有自环和重边。图不一定连通。

输出格式

输出一个整数,表示答案。

若图中没有简单环,任何正整数都满足整除条件,因而不存在最大的一个,此时按要求输出 0。

原样例 1

4 4
1 2 1
2 3 1
3 4 1
4 1 1
4

原样例 2

4 5
1 2 1
1 3 2
1 4 1
2 3 1
3 4 1
4