import sys readline=sys.stdin.readline class Graph: def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")): self.V=V self.directed=directed self.weighted=weighted self.inf=inf if graph: self.graph=graph self.edges=[] for i in range(self.V): if self.weighted: for j,d in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j,d)) else: for j in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j)) else: self.edges=edges self.graph=[[] for i in range(self.V)] if weighted: for i,j,d in self.edges: self.graph[i].append((j,d)) if not self.directed: self.graph[j].append((i,d)) else: for i,j in self.edges: self.graph[i].append(j) if not self.directed: self.graph[j].append(i) def SIV_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V finished=[False]*self.V if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if lowlink: order=[None]*self.V ll=[None]*self.V idx=0 if parents or cycle_detection or lowlink or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if unweighted_dist or bipartite_graph: uwd=[self.inf]*self.V uwd[s]=0 if weighted_dist: wd=[self.inf]*self.V wd[s]=0 stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc.append(x) if lowlink: order[x]=idx ll[x]=idx idx+=1 if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if parents or cycle_detection or lowlink or subtree_size: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d elif not finished[y]: if (directed_acyclic or cycle_detection or topological_sort) and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if lowlink: bl=True for y in self.graph[x]: if self.weighted: y,d=y if ps[x]==y and bl: bl=False continue ll[x]=min(ll[x],order[y]) if x!=s: ll[ps[x]]=min(ll[ps[x]],ll[x]) if postorder or topological_sort: post.append(x) if subtree_size: for y in self.graph[x]: if self.weighted: y,d=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg=[[],[]] for tpl in self.edges: x,y=tpl[:2] if self.weighted else tpl if uwd[x]==self.inf or uwd[y]==self.inf: continue if not uwd[x]%2^uwd[y]%2: bg=False break else: for x in range(self.V): if uwd[x]==self.inf: continue bg[uwd[x]%2].append(x) retu=() if bipartite_graph: retu+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) retu+=(cd,) if directed_acyclic: retu+=(dag,) if euler_tour: retu+=(et,) if linked_components: retu+=(lc,) if lowlink: retu=(ll,) if parents: retu+=(ps,) if postorder: retu+=(post,) if preorder: retu+=(pre,) if subtree_size: retu+=(ss,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] retu+=(tp_sort,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def MIV_DFS(self,initial_vertices=None,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False): if initial_vertices==None: initial_vertices=[s for s in range(self.V)] seen=[False]*self.V finished=[False]*self.V if bipartite_graph: bg=[None]*self.V cnt=-1 if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if lowlink: order=[None]*self.V ll=[None]*self.V idx=0 if parents or cycle_detection or lowlink or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if bipartite_graph or unweighted_dist: uwd=[self.inf]*self.V if weighted_dist: wd=[self.inf]*self.V for s in initial_vertices: if seen[s]: continue if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([]) if bipartite_graph or unweighted_dist: uwd[s]=0 if weighted_dist: wd[s]=0 stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc[-1].append(x) if lowlink: order[x]=idx ll[x]=idx idx+=1 if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if bipartite_graph: bg[y]=(cnt,bg[x][1]^1) if parents or cycle_detection or lowlink or subtree_size: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d elif not finished[y]: if directed_acyclic and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if lowlink: bl=True for y in self.graph[x]: if self.weighted: y,d=y if ps[x]==y and bl: bl=False continue ll[x]=min(ll[x],order[y]) if x!=s: ll[ps[x]]=min(ll[ps[x]],ll[x]) if postorder or topological_sort: post.append(x) if subtree_size: for y in self.graph[x]: if self.weighted: y,d=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg_=bg bg=[[[],[]] for i in range(cnt+1)] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if not bg_[i][1]^bg_[j][1]: bg[bg_[i][0]]=False for x in range(self.V): if bg[bg_[x][0]]: bg[bg_[x][0]][bg_[x][1]].append(x) retu=() if bipartite_graph: retu+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) retu+=(cd,) if directed_acyclic: retu+=(dag,) if euler_tour: retu+=(et,) if linked_components: retu+=(lc,) if lowlink: retu=(ll,) if parents: retu+=(ps,) if postorder: retu+=(post,) if preorder: retu+=(pre,) if subtree_size: retu+=(ss,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] retu+=(tp_sort,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def SIV_BFS(self,s,bfs_tour=False,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V seen[s]=True if bfs_tour: bt=[s] if linked_components: lc=[s] if parents: ps=[None]*self.V if unweighted_dist or bipartite_graph: uwd=[self.inf]*self.V uwd[s]=0 if weighted_dist: wd=[self.inf]*self.V wd[s]=0 queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) if bfs_tour: bt.append(y) if linked_components: lc.append(y) if parents: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d if bipartite_graph: bg=[[],[]] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if uwd[i]==self.inf or uwd[j]==self.inf: continue if not uwd[i]%2^uwd[j]%2: bg=False break else: for x in range(self.V): if uwd[x]==self.inf: continue bg[uwd[x]%2].append(x) retu=() if bfs_tour: retu+=(bt,) if bipartite_graph: retu+=(bg,) if linked_components: retu+=(lc,) if parents: retu+=(ps,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def MIV_BFS(self,initial_vertices=None,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False): if initial_vertices==None: initial_vertices=[i for i in range(self.V)] seen=[False]*self.V if bipartite_graph: bg=[None]*self.V cnt=-1 if linked_components: lc=[] if parents: ps=[None]*self.V if unweighted_dist: uwd=[self.inf]*self.V if weighted_dist: wd=[self.inf]*self.V for s in initial_vertices: if seen[s]: continue seen[s]=True if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([s]) if unweighted_dist: uwd[s]=0 if weighted_dist: wd[s]=0 queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) if bipartite_graph: bg[y]=(cnt,bg[x][1]^1) if linked_components: lc[-1].append(y) if parents: ps[y]=x if unweighted_dist: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d if bipartite_graph: bg_=bg bg=[[[],[]] for i in range(cnt+1)] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if not bg_[i][1]^bg_[j][1]: bg[bg_[i][0]]=False for x in range(self.V): if bg[bg_[x][0]]: bg[bg_[x][0]][bg_[x][1]].append(x) retu=() if bipartite_graph: retu+=(bg,) if linked_components: retu+=(lc,) if parents: retu=(ps,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def Build_Approach(self,s): self.approach_parents,self.approach_depth=self.SIV_DFS(s,parents=True,unweighted_dist=True) self.approach_parents[s]=s self.approach_PD=Path_Doubling(self.V,self.approach_parents) self.approach_PD.Build_Next() def Approach(self,x,y): if x==y: return None if self.approach_depth[x]>=self.approach_depth[y]: return self.approach_parents[x] retu=self.approach_PD.Permutation_Doubling(y,self.approach_depth[y]-self.approach_depth[x]-1) if self.approach_parents[retu]==x: return retu else: return self.approach_parents[x] def Build_Rerooting(self,s,f,f_merge,subtree=False): self.rerooting_s=s self.rerooting_f=f self.rerooting_f_merge=f_merge self.subtree=subtree if self.subtree: parents,postorder,preorder,self.rerooting_depth=self.SIV_DFS(s,parents=True,postorder=True,preorder=True,unweighted_dist=True) parents[s]=s self.rerooting_PD=Path_Doubling(self.V,parents) self.rerooting_PD.Build_Next() parents[s]=None else: parents,postorder,preorder=self.SIV_DFS(s,parents=True,postorder=True,preorder=True) self.rerooting_lower_dp=[None]*self.V for x in postorder: children=[y[0] if self.weighted else y for y in self.graph[x] if (y[0] if self.weighted else y)!=parents[x]] self.rerooting_lower_dp[x]=self.rerooting_f_merge(x,[self.rerooting_f(y,self.rerooting_lower_dp[y]) for y in children]) self.rerooting_upper_dp=[None]*self.V for x in preorder: children=[y[0] if self.weighted else y for y in self.graph[x] if (y[0] if self.weighted else y)!=parents[x]] left_accumule_f=[None]*(len(children)+1) right_accumule_f=[None]*(len(children)+1) left_accumule_f[0]=self.rerooting_f_merge(x,[]) for i in range(1,len(children)+1): left_accumule_f[i]=self.rerooting_f_merge(x,[left_accumule_f[i-1],self.rerooting_f(children[i-1],self.rerooting_lower_dp[children[i-1]])]) right_accumule_f[len(children)]=self.rerooting_f_merge(x,[]) for i in range(len(children)-1,-1,-1): right_accumule_f[i]=self.rerooting_f_merge(x,[right_accumule_f[i+1],self.rerooting_f(children[i],self.rerooting_lower_dp[children[i]])]) for i in range(len(children)): if parents[x]==None: self.rerooting_upper_dp[children[i]]=self.rerooting_f(x,self.rerooting_f_merge(x,[left_accumule_f[i],right_accumule_f[i+1]])) else: self.rerooting_upper_dp[children[i]]=self.rerooting_f(x,self.rerooting_f_merge(x,[left_accumule_f[i],right_accumule_f[i+1],self.rerooting_upper_dp[x]])) if self.subtree: self.rerooting_parents=parents def Rerooting(self,root,subtree=None): if self.subtree and root!=subtree: if self.rerooting_depth[subtree]>=self.rerooting_depth[root]: x=self.rerooting_parents[subtree] else: x=self.rerooting_PD.Permutation_Doubling(root,self.rerooting_depth[root]-self.rerooting_depth[subtree]-1) if self.rerooting_parents[x]!=subtree: x=self.rerooting_parents[subtree] if self.rerooting_parents[subtree]==x: retu=self.rerooting_f(subtree,self.rerooting_lower_dp[subtree]) else: retu=self.rerooting_upper_dp[x] else: if root==self.rerooting_s: retu=self.rerooting_f(root,self.rerooting_lower_dp[root]) else: retu=self.rerooting_f(root,self.rerooting_f_merge(root,[self.rerooting_lower_dp[root],self.rerooting_upper_dp[root]])) return retu def XOR_Basis(lst): xor_basis=[] triangulation=[] for i,x in enumerate(lst): xx=x for j,xb in enumerate(triangulation): if xx>xx^xb: xx=xx^xb if xx: xor_basis.append(x) for j in range(len(triangulation)): if triangulation[j]^xx>i&1: N=self.permutation_doubling[N][i] return N def Doubling(self,N,K): if K<0: return self.e retu=self.e for i in range(self.k): if K>>i&1: retu=self.f(retu,self.doubling[N][i]) N=self.permutation_doubling[N][i] return retu N=int(readline()) edges=[] W={} for n in range(N-1): u,v,w=map(int,readline().split()) u-=1;v-=1 edges.append((u,v,w)) W[(u,v)]=w W[(v,u)]=w mod=10**9+7 def f(x,tpl): d0,d1,d2=tpl return x,d0+1,d1,d2 def f_merge(x,lst): D0,D1,D2=0,0,0 for tpl in lst: if len(tpl)==3: d0,d1,d2=tpl D0+=d0 D1+=d1 D2+=d2 else: y,d0,d1,d2=tpl w=W[(x,y)] D0+=d0 D1+=d1+w*d0%mod D2+=d2+2*d1*w%mod+w*w*d0%mod D1%=mod D2%=mod return D0,D1,D2 G=Graph(N,edges=edges,weighted=True) G.Build_Rerooting(0,f,f_merge,subtree=True) ans=0 for x in range(N): ans+=G.Rerooting(x,x)[3] inve2=(1+mod)//2 ans*=inve2 ans%=mod ans%=mod print(ans)