题目描述

云浅有一颗 $n$ 个点的树，每条边有边权。定义两个点 $i,j$ 配对的代价为 $i,j$ 之间唯一路径上的边权和。

现在 Yoimiya 拿出了一个长度为偶数的区间 $[l,r]$，她想要把编号在 $[l,r]$ 内的点两两配对，并最小化这些点配对的代价之和。定义这个区间 $[l,r]$ 的权值就是将 $l,l+1,\cdots,r$ 两两配对的最小代价和。

Yoimiya 想让你求出所有长度为偶数的区间的权值之和对 $2^{32}$ 取模的值。

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行，第 $i+1$ 行有三个正整数 $u_i,v_i,w_i$ 表示树上的一条边。

输出格式

输出一行一个非负整数表示答案。

样例 $1$ 输入

5
1 2 2
1 3 4
2 4 5
2 5 3

样例 $1$ 输出

50

样例 $1$ 解释

区间 $[1,2],[2,3],[3,4],[4,5]$ 的权值分别是 $2,6,11,8$。

区间 $[1,4]$ 的权值是 $9$，一种最优方案是把 $(1,3),(2,4)$ 分别配对。

区间 $[2,5]$ 的权值是 $14$，一种最优方案是把 $(2,4),(3,5)$ 分别配对。

故所有长度为偶数的区间的权值和为 $2+6+11+8+9+14=50$。

样例 $2,3,4,5$

Yoimiya 很善良，她送了你四个小样例帮助你调试。

见附加文件中的 glacies2/3/4/5.in 与 glacies2/3/4/5.ans。

其中 glacies4.in 满足特殊性质 A，glacies5.in 满足特殊性质 B。

附加文件下载

数据范围与约束

对于所有数据，$2\le n\le 2\times 10^5,1\le w_i\le 10^9,1\le u_i,v_i\le n$。

• 特殊性质 A：$u_i=i,v_i=i+1$。
• 特殊性质 B：树是一条链，即存在长为 $n$ 的排列 $p$，使得对任意的 $1\le i<n$，树上均存在边 $(p_i,p_{i+1})$。
• 特殊性质 C：$u_i$ 在 $[1,i]$ 中均匀随机选取，$v_i=i+1$。