#pragma GCC target ("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ld = long double; using H = pair; using P = pair; using vi = vector; #define all(a) (a).begin(),(a).end() #define fs first #define sc second #define xx first #define yy second.first #define zz second.second #define Q(i,j,k) mkp(i,mkp(j,k)) #define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++) #define rep(i,n) rng(i, 0, (n)) #define mkp make_pair #define vec vector #define pb emplace_back #define siz(a) int(a.size()) #define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end()) #define getidx(b,i) (lower_bound(all(b),(i))-(b).begin()) #define ssp(i,n) (i==(ll)(n)-1?"\n":" ") #define ctoi(c) (int)(c-'0') #define itoc(c) (char)(c+'0') #define cyes printf("Yes\n") #define cno printf("No\n") #define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--) #define gcj printf("Case #%lld: ",qq123_+1) #define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read() #define found(a,x) (a.find(x)!=a.end()) constexpr ll mod = (ll)1e9 + 7; constexpr ll Mod = 998244353; constexpr ld EPS = 1e-10; constexpr ll inf = (ll)3 * 1e18; constexpr int Inf = (ll)15 * 1e8; constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 }; templatebool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } ll read() { ll u, k = scanf("%lld", &u); return u; } string reads() { string s; cin >> s; return s; } H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; } bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; } bool ina(int t, int l, int r) { return l <= t && t < r; } ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; } ll ppc(ll x) { int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++; return sum; } void fin1() { printf("-1\n"); exit(0); } void fin0() { printf("0\n"); exit(0); } template class csum { vec v; public: csum(vec& a) :v(a) { build(); } csum() {} csum(int sz) { init(sz); } void init(int sz) { v = vector(sz + 1, 0); } void init(vec& a) { v = a; build(); } void build() { for (int i = 1; i < v.size(); i++) v[i] += v[i - 1]; } void add(int l, int r, T x) { v[l] += x; v[r] -= x; }//[l,r) void add(int t, T x) { v[t] += x; }//[l,r) //[l,r] T a(int l, int r) { if (r < l) return 0; return v[r] - (l == 0 ? 0 : v[l - 1]); } //[l,r) T b(int l, int r) { return a(l, r - 1); } T a(pairt) { return a(t.first, t.second); } T b(pairt) { return b(t.first, t.second); } T operator[](int x)const { return v[x]; } }; template class modint { public:ll v; modint(ll v = 0) { s(v % mod + mod); } constexpr static int fn_ = (ll)2e6 + 5; static vectorfact, comp; modint pow(ll x) const { modint b(v), c(1); while (x) { if (x & 1) c *= b; b *= b; x >>= 1; } return c; } inline modint& s(int vv) { v = vv < mod ? vv : vv - mod; return *this; } inline modint inv()const { return pow(mod - 2); } inline modint operator-()const { return modint() - *this; } inline modint& operator+=(const modint b) { return s(v + b.v); } inline modint& operator-=(const modint b) { return s(v + mod - b.v); } inline modint& operator*=(const modint b) { v = v * b.v % mod; return *this; } inline modint& operator/=(const modint b) { v = v * b.inv().v % mod; return *this; } inline modint operator+(const modint& b) const { return modint(v) += b; } inline modint operator-(const modint& b) const { return modint(v) -= b; } inline modint operator*(const modint& b) const { return modint(v) *= b; } inline modint operator/(const modint& b) const { return modint(v) /= b; } friend ostream& operator<<(ostream& os, const modint& m) { return os << m.v; } friend istream& operator>>(istream& is, modint& m) { int x; is >> x; m = modint(x); return is; } bool operator<(const modint& r)const { return v < r.v; } bool operator>(const modint& r)const { return v > r.v; } bool operator<=(const modint& r)const { return v <= r.v; } bool operator>=(const modint& r)const { return v >= r.v; } bool operator==(const modint& r)const { return v == r.v; } bool operator!=(const modint& r)const { return v != r.v; } explicit operator bool()const { return v; } explicit operator int()const { return v; } modint comb(modint k) { if (k > *this) return modint(); if (fact.empty()) combinit(); if (v >= fn_) { if (k > *this - k) k = *this - k; modint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i); return tmp * comp[k.v]; } return fact[v] * comp[k.v] * comp[v - k.v]; }//nCk modint perm(modint k) { if (k > *this) return modint(); if (fact.empty()) combinit(); if (v >= fn_) { modint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i); return tmp; } return fact[v] * comp[v - k.v]; }//nPk static void combinit() { fact.assign(fn_, modint()); fact[0] = 1; for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * modint(i); comp.assign(fn_, modint()); comp[fn_ - 1] = fact[fn_ - 1].inv(); for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * modint(i + 1); } }; using mint = modint; template<>vec mint::fact = vec(); template<>vec mint::comp = vec(); //-------------------------------------------------------------- //-------------------------------------------------------------- ll n; vece[300000]; ll cnt[300000]; mint dp[300000]; signed main() { cin >> n; rep(i, n - 1) { int u, v, w; cin >> u >> v >> w; u--; v--; e[u].pb(H{ v,w }); e[v].pb(H{ u,w }); } auto dfs = [&](int x, int p, ll cst, auto& dfs) ->pair { ll sum = 0; mint ret = 0; for (auto g : e[x]) { if (g.fs == p) continue; auto t = dfs(g.fs, x, g.sc, dfs); sum += t.fs; ret += t.sc; } if (x > 0) { cnt[x] = sum + 1; dp[x] = ret; } return mkp(sum + 1, ret + (sum + 1) * cst); }; dfs(0, -1, 0, dfs); mint ans = 0; auto dfs2 = [&](int x, int p, ll cst, mint r, auto& dfs2)->void { //とりあえずここを求める if (x > 0) { ans += mint(cst) * cst *cnt[x] * (n - cnt[x]); ans += (r * cnt[x] + dp[x] * (n - cnt[x]))* cst; } vec d; vi h; for (auto g : e[x]) { if (g.fs != p) { d.pb(dp[g.fs] + (cnt[g.fs] * g.sc)); h.pb(cnt[g.fs]); } else d.pb(0), h.pb(0); } csumc(d); csumf(h); rep(i, siz(e[x])) { if (e[x][i].fs == p) continue; dfs2(e[x][i].fs, x, e[x][i].sc, r + c.b(0, i) + c.b(i + 1, siz(e[x])) + cst * (n - cnt[x]), dfs2); //x==0 } }; dfs2(0, -1, 0, 0, dfs2); cout << ans << endl; }