链接: https://cses.fi/problemset/task/3111

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一个计算机网络有 $n$ 台计算机和 $n-1$ 条它们之间的连接。利用这些连接，任意两台计算机之间都能交换信息。

每条连接都有一个特定的传输速度。令 $d(a,b)$ 表示计算机 $a$ 与 $b$ 之间的传输速度，即 $a$ 到 $b$ 的路线上最慢那条连接的速度。你的任务是计算所有计算机对之间的传输速度之和。

输入

第一行包含整数 $n$：计算机数量。计算机编号为 $1,2,\dots,n$。

接下来有 $n-1$ 行描述连接。每行包含三个整数 $a$、$b$ 和 $x$：表示计算机 $a$ 与 $b$ 之间有一条传输速度为 $x$ 的连接。

输出

输出一个整数：传输速度之和。

数据范围

$1 \le n \le 2 \cdot 10^5$ $1 \le x \le 10^6$

样例输入

4
1 2 5
2 3 1
2 4 2

样例输出

12