Many Many Cycles

Time limit2sMemory limit2048 MB

Summary

Given a weighted undirected graph, find the largest d that divides the length of every simple cycle, or 0 if no such d exists.

Level: Medium7 of 10
Topics: Graph, DFS, Number theory
Solved: No attempts yet

Problem

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$ .

Input

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$ ). The graph has no loops or multiple edges.

Output

Print one integer: the answer to the problem.

Examples2

Example 1
Input
```
4 4
1 2 1
2 3 1
3 4 1
4 1 1
```
Expected output
```
4
```
Example 2
Input
```
4 5
1 2 1
1 3 2
1 4 1
2 3 1
3 4 1
```
Expected output
```
4
```