#include using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #include using namespace atcoder; using mint=modint1000000007; ostream& operator<<(ostream &os,mint a){os<>(istream &is,mint &a){ long long b;is>>b;a=b; return is; } class IntegerSumRuleUnionFind{ using ll=long long; int n,num; vector sz,parent; vector> potential; vector> value; public: IntegerSumRuleUnionFind()=default; IntegerSumRuleUnionFind(int n):n(n),num(n),sz(n,1),parent(n,0),potential(n,{1,0}),value(n,nullopt){ iota(parent.begin(),parent.end(),0); } tuple from_root(int x){ if(x==parent[x])return {x,1,0LL}; auto [r,a,b]=from_root(parent[x]); auto [c,d]=potential[x]; parent[x]=r; potential[x]={a*c,b*c+d}; return {r,a*c,b*c+d}; } int leader(int x){ return get<0>(from_root(x)); } bool same(int x,int y){ assert(0<=x and x val(int x){ auto [r,a,b]=from_root(x); if(value[r])return value[r].value()*a+b; return nullopt; } // x と y が隣接してないなら nullopt // x と y が隣接しているが、sum が一意でない場合も nullopt optional sum(int x,int y){ auto [rx,a,b]=from_root(x); auto [ry,c,d]=from_root(y); if(rx!=ry)return nullopt; if(a==c){ assert(b==d); return nullopt; } return b+d; } int size(const int x){ assert(0<=x and x>n>>m>>k; IntegerSumRuleUnionFind UF(n); REP(_,m){ int x,y,z;cin>>x>>y>>z;x--;y--; if(!UF.merge(x,y,z)){ cerr<<0< low(n,1),high(n,upper); REP(i,n){ auto [r,a,b]=UF.from_root(i); if(UF.val(r)){ ll v=UF.val(r).value()*a+b; if(v<1||upper