题目描述

给定一张$N$个点$M$条边的无向图，求图中所有生成树边权最大公约数的最小公倍数。

输入

第一行有两个整数$N,M$，分别表示点数和边数。 接下来$M$行每行有三个整数$s_i,t_i,d_i$，表示点$s_i$与点$t_i$间存在一条权为$d_i$的边，保证$s_i$不等于$t_i$。

输出

所求的最小公倍数$ans$。

输入样例

3 3
1 2 2
2 3 3
1 3 6

输出样例

6

提示

(解释：有$3$个合法的生成树，它们的边权最大公约数分别为$1,2,3$,它们的最小公倍数为$6$） 【数据规模】 对于20%的数据，$M=N-1$； 对于另外20%的数据，$M=N$； 对于另外30%的数据，所有边权都是$2$ 的整数次幂； 对于100%的数据，$N≤1000，M≤100000，d_i≤2^{15}-1，ans≤2^{64}-1$。

完整数据范围与边界约定

2≤N≤1000，0≤M≤100000，端点1..N且不同，1≤d_i≤32767，允许重边。若图不连通，没有生成树，约定输出0；否则求所有生成树边权GCD的LCM，并保证该LCM≤2^64-1。不同生成树允许分别提供不同素因子的最高指数。