Given a connected graph of nodes and weighted bidirectional edges, print the maximum Greatest Common Divisor (GCD) of the weights of the edges of any connected subgraph. A connected subgraph is a graph such that there is at least 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, .
The next lines will each contain three integers, . 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 edges.
Sample Input
4 5
1 3 3
3 4 8
1 4 4
1 2 6
2 4 12
Sample Output
4
Comments