2699: 防贼道路

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