시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB369619.355%

문제

Consider an undirected graph $G$. Find the maximal number $d$ such that the lengths of all simple cycles are divisible by $d$. If there is no such number, output $0$.

입력

The first line contains two integers $n$ and $m$: the number of vertices and edges ($1 \le n \le 5000$, $0 \le m \le 10\,000$). Each of the next $m$ lines contains three integers $a$, $b$, and $c$, which mean that there is a bidirectional edge between vertices $a$ and $b$ with length $c$ ($1 \le a, b \le n$, $1 \le c \le 10^9$). It is guaranteed that the graph doesn't contain loops or multiple edges.

출력

Print one integer: the answer to the problem.

예제 입력 1

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

예제 출력 1

4

예제 입력 2

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

예제 출력 2

4