题目背景

你未曾料到，烟火散尽，余烬渐冷，那一转身的轻易告别，却成了永远的诀别。

但是，你决意追寻她的身影，哪怕在这永无止境的重逢梦中。

题目描述

$n$ 个地点构成了复杂的关系网。

但是现在这些地点复杂的路线关系被简化成为了一棵树。

你从每个点均出发一次，当你从点 $u$ 出发时，你会找到这个点能到达的所有最远点 $v_1,v_2,\cdots v_k$，并对每个 $v_i$，将 $u$ 到 $v_i$ 简单路径上的点权值加 $1$。

询问最终所有地点的权值总和。

输入格式

本题输入均为正整数。

第一行一个数 $n$，表示有 $n$ 个地点。

接下来 $n−1$ 行，每行三个整数 $a_i,b_i,w_i$ 表示一条边。

输出格式

一行一个数，表示所有地点最后的权值总和。

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

44

10
6 10 3
9 5 4
6 7 10
6 5 9
10 4 8
5 1 9
8 10 10
2 7 1
3 1 3

52

提示

样例一解释：

从 $1$ 出发，最远距离为 $3$，故到达 $5$ 和 $6$，各点权为 $[2,2,0,2,1,1]$；

从 $2$ 出发，最远距离为 $2$，故到达 $5$ 和 $6$，各点权为 $[2,4,0,4,2,2]$；

从 $3$ 出发，最远距离为 $3$，故到达 $5$ 和 $6$，各点权为 $[2,6,2,6,3,3]$；

从 $4$ 出发，最远距离为 $2$，故到达 $1$ 和 $3$，各点权为 $[3,8,3,8,3,3]$；

从 $5$ 出发，最远距离为 $3$，故到达 $1$ 和 $3$，各点权为 $[4,10,4,10,5,3]$；

从 $6$ 出发，最远距离为 $3$，故到达 $1$ 和 $3$，各点权为 $[5,12,5,12,5,5]$。

所以最终各点权和为 $44$。

（黄色为 $1$ 出发的路径；红色为 $2$；蓝色为 $3$；绿色为 $4$；青色为 $5$；紫色为 $6$。）

---

本题采用捆绑测试。

• Subtask 1（20 points，1 s）：$1\le n \le 5000$。
• Subtask 2（40 points，1 s）：$1\le n \le 5\times 10^5$。
• Subtask 3（10 points，1 s）：树的形态为链。
• Subtask 4（10 points，2 s）：树的形态为菊花。
• Subtask 5（20 points，2 s）：无特殊限制。

对于所有测试数据，$1\le n\le 10^6$，$1\le w_i \le 10^9$，$1\le a_i \le n$，$1 \le b_i\le n$。

本题输入数据较大，请使用较快的读入方式和实现方式。请注意本题的栈空间。