生成树

【题目描述】

给定一张$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$。