Given a connected graph of ~N~ nodes and ~M~ weighted bidirectional edges, print the maximum Greatest Common Divisor (GCD) of the weights of the edges of any connected subgraph. A connnected subgraph is a graph such that there is at least ~1~ path between any two nodes, and all edges in the subgraph are in the original graph.

Input Specification

The first line will contain two integers, ~N, M~ ~(2 \le N \le 10^4, 1 \le M \le 10^5)~.

The next ~M~ lines will each contain three integers, ~u, v, w~ ~(1 \le u, v \le N, u \neq v, 1 \le w \le 10^3)~. There may be more than one edge between any two nodes.

Output Specification

Output the maximum GCD of the weights of the edges of any subgraph that can be constructed with the ~M~ edges.

Sample Input

4 5
1 3 3
3 4 8
1 4 4
1 2 6
2 4 12

Sample Output

4