문제

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.

제한

힌트