```cpp
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int u[3005],v[3005],w[3005],vist[3005],a[61][61];
int s[1000005],mo[1000005],d[1000005],f[1000005],tot=0;
void print()
{
s[1]=mo[1]=1;
for(int i=2;i<=1000000;i++)
{
if(!s[i])d[++tot]=i,mo[i]=-1;
for(int j=1;j<=tot&&i*d[j]<=1000000;j++)
{
s[i*d[j]]=1;
if(i%d[j]==0)
{
mo[i*d[j]]=0;
break;
}
mo[i*d[j]]=-mo[i];
}
}
}
int hls(int n)
{
int r=0;
for(int i=1;i<=n;i++)
{
int w=0;
for(int j=i;j<=n;j++)if(a[j][i])w=j;
if(!w)return 0;
for(int j=1;j<=n;j++)swap(a[i][j],a[w][j]);
if(i!=w)r++;
for(int j=i+1;j<=n;j++)
{
while(a[j][i])
{
r++;
if(a[i][i]==0)
{
for(int k=1;k<=n;k++)swap(a[i][k],a[j][k]);
break;
}
int gg=-a[j][i]/a[i][i];
for(int k=1;k<=n;k++)a[j][k]=(a[j][k]+1ll*gg*a[i][k])%mod;
for(int k=1;k<=n;k++)swap(a[i][k],a[j][k]);
}
}
}
int ans=1;
if(r&1)ans=-1;
for(int i=1;i<=n;i++)ans=1ll*ans*a[i][i]%mod;
return ans;
}
int main()
{
print();
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)scanf("%d%d%d",&u[i],&v[i],&w[i]);
for(int i=1;i<=1000000;i++)
{
int gs=0;
for(int j=1;j<=m;j++)
{
if(w[j]%i==0)vist[j]=1,gs++;
else vist[j]=0;
}
if(gs<n-1)continue;
memset(a,0,sizeof(a));
for(int j=1;j<=m;j++)if(vist[j])
a[u[j]][u[j]]++,a[v[j]][v[j]]++,a[u[j]][v[j]]--,a[v[j]][u[j]]--;
f[i]=hls(n-1);
}
long long ans=0;
for(int i=1;i<=1000000;i++)for(int j=1;i*j<=1000000;j++)
ans+=1ll*i*mo[j]*f[i*j]%mod;
cout<<(ans%mod+mod)%mod<<endl;
return 0;
}
```
by wmy_goes_to_thu @ 2021-03-18 19:02:18