梦想赛道

题号：NC228136
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

给出一个 $n$ 个点的有边权的树，求一个图满足给出的树是图上的一个 严格次小生成树（注意原树上的边权不能改变） 且该图的所有边权和最小，并且要求所有的边权都是正整数。

严格次小生成树: 即在所有生成树中，该生成树是权值大于最小生成树的生成树中权值最小的其中一棵。

第一行一个正整数 $n$ $(2\leq n\leq 5\times 10^5)$ 表示树的点数

接下来 $n-1$ 行，每行包括三个正整数 $x,y,w$ $(1\leq x,y\leq n,1\leq w\leq 10^3)$ ，表示树上有一条权值为 $w$ 的边连接 $x$ 和 $y$ 。

第一行输出一个数表示满足条件的图的最小边权和。如果无解，则输出  。

示例1

复制

3
1 2 1
2 3 2

复制

在 (1,3) 或 (2,3) 两点之间添加一条边权为 1 的边都可以满足条件。

图中允许有重边。