先对三进制下的每一位进行考虑，类似 CF917D Stranger Trees 一样，对每条边赋权为 (1,x,x^2)，矩阵树定理求行列式后用高斯消元或者插值求出多项式即可，但这样复杂度为 (O(n^4 log n))。因为循环卷积意义下的多项式的有用次数比较小，考虑直接代入多项式来求行列式，这里多项式的运算为模 (x^3) 意义下的循环卷积，代入 (3) 次单位根即可， (3) 次单位根有个性质：(omega_3^2=omega_3-1)，用二元组 ((a,b)) 来表示一个数 (a+bomega_3)，得其逆元为：
[large frac{1}{a+bomega_3}=frac{a-b-bomega_3}{(a+bomega_3)(a-b-bomega_3)}=frac{a-b}{a^2+b^2-ab}-frac{b}{a^2+b^2-ab}omega_3
]
实际上因为 (3) 在本题的模数中存在二次剩余，因此二元组 ((a,b)) 也可以直接表示复数 (a+bi)。总复杂度为 (O(n^3log n))。
#include<bits/stdc++.h>
#define maxn 210
#define maxm 40010
#define p 1000000007
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,mx;
ll ans;
struct edge
{
int x,y,v;
edge(int a=0,int b=0,int c=0)
{
x=a,y=b,v=c;
}
}e[maxm];
ll inv(ll x)
{
ll v=1,y=p-2;
while(y)
{
if(y&1) v=v*x%p;
x=x*x%p,y>>=1;
}
return v;
}
struct node
{
ll a,b;
node(ll x=0,ll y=0)
{
a=x,b=y;
}
node get()
{
ll v=inv(a*a%p+b*b%p-a*b%p+p);
return node((a-b+p)*v%p,(p-b)*v%p);
}
bool empty()
{
return !a&&!b;
}
}a[maxn][maxn],w[5],f[5],g[5];
node operator + (const node &x,const node &y)
{
return node((x.a+y.a)%p,(x.b+y.b)%p);
}
node operator - (const node &x,const node &y)
{
return node((x.a-y.a+p)%p,(x.b-y.b+p)%p);
}
node operator * (const node &x,const node &y)
{
return node((x.a*y.a%p-x.b*y.b%p+p)%p,(x.a*y.b%p+x.b*y.a%p-x.b*y.b%p+p)%p);
}
node det()
{
node v=node(1,0);
for(int i=2;i<=n;++i)
{
if(a[i][i].empty())
{
for(int j=i+1;j<=n;++j)
{
if(!a[j][i].empty())
{
swap(a[i],a[j]),v=node(0,0)-v;
break;
}
}
}
if(a[i][i].empty()) return node(0,0);
node iv=a[i][i].get();
for(int j=i+1;j<=n;++j)
{
node d=a[j][i]*iv;
for(int k=i;k<=n;++k) a[j][k]=a[j][k]-a[i][k]*d;
}
v=v*a[i][i];
}
return v;
}
int main()
{
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
read(n),read(m),w[0]=w[3]=node(1,0),w[1]=node(0,1),w[2]=node(p-1,p-1);
for(int i=1;i<=m;++i)
read(e[i].x),read(e[i].y),read(e[i].v),mx=max(mx,e[i].v);
for(int k=1;k<=mx;k*=3)
{
for(int i=0;i<3;++i)
{
memset(a,0,sizeof(a));
for(int j=1;j<=m;++j)
{
int x=e[j].x,y=e[j].y;
node v=w[e[j].v/k%3*i%3];
a[x][x]=a[x][x]+v,a[y][y]=a[y][y]+v;
a[x][y]=a[x][y]-v,a[y][x]=a[y][x]-v;
}
f[i]=det(),g[i]=node(0,0);
}
for(int i=0;i<3;++i)
for(int j=2;j>=0;--j)
g[i]=g[i]*w[3-i]+f[j];
ans=(ans+(g[1].a+g[2].a*2)*inv(3)%p*k%p)%p;
}
printf("%lld",ans);
return 0;
}