3280: 防贼道路
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
A国有N个城市，M条双向道路(所有城市都是连通的)，每条道路都有相应的价值，由于A国盗贼出没比较频繁，所以国王决定只保留一些道路，使得任意两座城市只有一条简单路径连通。假设T是其中一种合法的方案，那么P(T)代表的是合法方案中所有道路价值的最大公约数。国王想借此机会了解一下你的数学能力，所以你需要在一秒内回答他所有P(T)的最小公倍数的大小。
输入
第一行N M，表示城市数量，道路数量。 接下来M行s t d 表示城市s与城市t间存在一条价值为d的道路，保证s不等于t。
输出
所求的最小公倍数ans
样例输入 复制
3 3
1 2 2
2 3 3
1 3 6样例输出 复制
6提示
(解释：有3个合法的方案，P(T)分别为1,2,3,它们的最小公倍数为6）
20%：M=N-1 另外20%：M=N 另外30%：所有道路的价值都是2 的整数次幂 100%：N<=1000，M<=100000，Di<=2^15-1，ans<=2^64-1