背景

琉璃最近沉迷于《Maschera》的二次创作。

题目描述

琉璃小说中的世界有 $n$ 座城市，其中有 $n-1$ 条道路，不包含重边、自环。这 $n-1$ 条道路中，第 $i$ 条道路的魔力值为 $w_i$。

琉璃作为夜魔女王，她决定要观光整个黑暗世界 。她每次会随机选一个城市为起点，经过不少于 $L$ 条且不多于 $R$ 条道路后在一个城市为终点结束。她在观光的时候是不走回头路的。若琉璃每次观光中经过道路的魔力值依次为 $v_1,v_2,...,v_k(L\leq k\leq R)$，那么她会获得 $\max(v_1,v_2,...,v_k)$ 的魔力值。

现在琉璃想知道，她尝试了所有合法的观光路线后，她所获得的魔力值总和为多少。

注意，$x$ 到 $y$ 的路径和 $y$ 到 $x$ 的路径视为两条路径。

输入格式

第一行三个数 $n,L,R$。

接下来 $n-1$ 行，每行三个数 $x,y,w$，表示 $x$ 结点和 $y$ 结点之间有一条魔力值为 $w$ 的道路。

输出格式

输出她所获得的魔力值总和。

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

40

提示

数据范围：

对于 $10\%$ 的数据，$n\leq 5000$。

另有 $10\%$ 的数据，$\min(x,y)=1$。

另有 $15\%$ 的数据，$|x-y|=1$。

另有 $25\%$ 的数据，$L=1,R=n-1$。

对于 $100\%$ 的数据，$n\leq 10^5,1\leq L\leq R\leq n-1,1\leq w_i\leq 10^5$。