#line 1 "c.cpp" #include #include #define rep(i,n) for (int i = 0; i < int(n); ++i) #define repp(i,n,m) for (int i = m; i < int(n); ++i) #define reb(i,n) for (int i = int(n)-1; i >= 0; --i) #define all(v) v.begin(),v.end() using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; using ld = long double; using P = pair; using PL = pair; using pdd = pair; using pil = pair; using pli = pair; templateistream &operator>>(istream &is,vector &v){for(auto &e:v)is>>e;return is;} templatebool range(T a,T b,T x){return (a<=x&&xbool rrange(T a,T b,T c,T d,T x,T y){return (range(a,c,x)&&range(b,d,y));} templatevoid rev(vector &v){reverse(v.begin(),v.end());} void revs(string &s) {reverse(s.begin(),s.end());} templatevoid sor(vector &v, int f=0){sort(v.begin(),v.end());if(f!=0) rev(v);} templatebool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} templatebool chmax(T &a,const T &b){if(avoid uniq(vector &v){sor(v);v.erase(unique(v.begin(),v.end()),v.end());} templatevoid print(pair a); templatevoid print(vector v); templatevoid print(vector> v); void print(){ putchar(' '); } void print(bool a){ printf("%d", a); } void print(int a){ printf("%d", a); } void print(long a){ printf("%ld", a); } void print(long long a){ printf("%lld", a); } void print(char a){ printf("%c", a); } void print(char a[]){ printf("%s", a); } void print(const char a[]){ printf("%s", a); } void print(long double a){ printf("%.15Lf", a); } void print(const string& a){ for(auto&& i : a) print(i); } void print(unsigned int a){ printf("%u", a); } void print(unsigned long long a) { printf("%llu", a); } template void print(const T& a){ cout << a; } int out(){ putchar('\n'); return 0; } template int out(const T& t){ print(t); putchar('\n'); return 0; } template int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; } templatevoid print(pair a){print(a.first);print(),print(a.second);} templatevoid print(vector v){for(auto ite=v.begin();ite!=v.end();){print(*ite);if(++ite!=v.end())print();}} templatevoid print(vector> v){for(auto ite=v.begin();ite!=v.end();){print(*ite);if(++ite!=v.end())out();}} void yes(){out("Yes");} void no (){out("No");} void yn (bool t){if(t)yes();else no();} void fast_io(){cin.tie(0); ios::sync_with_stdio(0); cout< dx = {0,1,0,-1,1,1,-1,-1}; const vector dy = {1,0,-1,0,1,-1,-1,1}; const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string alp = "abcdefghijklmnopqrstuvwxyz"; const string NUM = "0123456789"; } // namespace noya2 using namespace noya2; using mint = modint1000000007; void out(mint a){out(a.val());} void out(vector a){vector b(a.size()); rep(i,a.size()) b[i] = a[i].val(); out(b);} void out(vector> a){for (auto v : a) out(v);} istream &operator>>(istream &is,vector &v){for(auto &e:v){ll _x;is>>_x;e=_x;}return is;} #line 2 "Rerooting.hpp" #line 4 "Rerooting.hpp" namespace noya2 { using namespace std; template struct Rerooting { struct edge{ int from, to, idx, rev_idx; }; Rerooting (int _n = 0) : n(_n) { es.resize(n);} void add_edge(int u, int v, int idx1, int idx2){ es[u].push_back({u,v,idx1,idx2}); es[v].push_back({v,u,idx2,idx1}); } V build(int v = 0){ root = v; vis.resize(n,0); outs.resize(n); return dfs(root); } vector reroot(){ reverse_edge.resize(n); reverse_edge[root] = e(); answers.resize(n); bfs(root); return answers; } private: int n, root; vector> es; vector vis; vector> outs; vector reverse_edge; vector answers; V dfs(int v){ vis[v]++; E val = e(); for (auto &p : es[v]){ if (vis[p.to] > 0 && p.to != es[v].back().to) swap(p,es[v].back()); if (vis[p.to] > 0) continue; E nval = put_edge(dfs(p.to),p.idx); outs[v].emplace_back(nval); val = merge(val,nval); } return put_vertex(val,v); } void bfs(int v){ int siz = outs[v].size(); vector lui(siz+1), rui(siz+1); lui[0] = e(), rui[siz] = e(); for (int i = 0; i < siz; i++) lui[i+1] = merge(lui[i],outs[v][i]); for (int i = siz-1; i >= 0; i--) rui[i] = merge(outs[v][i],rui[i+1]); for (int i = 0; i < siz; i++){ reverse_edge[es[v][i].to] = put_edge(put_vertex(merge(merge(lui[i],rui[i+1]),reverse_edge[v]),v),es[v][i].rev_idx); bfs(es[v][i].to); } answers[v] = put_vertex(merge(lui[siz],reverse_edge[v]), v); } }; } // namespace noya2 #line 78 "c.cpp" vector a; struct S{ mint s, s2, siz; }; S op(S a, S b){ S c; c.siz = a.siz + b.siz; c.s = a.s + b.s; c.s2 = a.s2 + b.s2; return c; } S e(){return S{0,0,0};} S pute(S x, int i){ S y; y.siz = x.siz; y.s = x.s + a[i] * x.siz; y.s2 = x.s2 + 2 * a[i] * x.s + a[i] * a[i] * x.siz; return y; } S putv(S x, int v){ x.siz += 1; return x; } void solve(){ int n; cin >> n; a.resize(n-1); Rerooting g(n); rep(i,n-1){ int u, v; cin >> u >> v; ll c; cin >> c; a[i] = c; g.add_edge(u-1,v-1,i,i); } g.build(); mint ans = 0; for (auto x : g.reroot()) ans += x.s2; ans /= 2; out(ans.val()); } int main(){ fast_io(); int t = 1; //cin >> t; while(t--) solve(); }