换根DP
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一棵 n 个节点的无根树，其中边权只有 1 或 2 两种。

现在定义 u \to v两点之间的距离 w \left(u, v \right ) 为两点间简单路径上所有边权的最大公约数。令 f (t) 表示为节点 t 到树上其他节点的距离之和。

求 \min (f(1), f(2), \dots, f(n))。

输入描述:

第一行包含一个正整数 n (1 \le n \le 10^{5})，代表这棵树的节点数量。

接下来 n - 1 行，每行三个正整数 u, v, w (1 \le u, v \le n, 1\le w \le 2)，代表 u 和 v 之间有一条权值为 w 的无向边。

输出描述:

输出一行一个正整数，代表\min( f(1), f(2), f(3) \dots f(n))。
示例1

输入

复制 
5
1 2 2
2 3 2
1 4 1
4 5 2

输出

复制 
5

说明

以节点 4 作根时， f(4) = w(4, 1) + w(4, 2) + w(4, 3) + w(4, 5) = gcd(1, 2) + gcd(1, 2, 2) + 1 + 2 = 1 + 1 + 1 + 2 = 5

可以证明，没有比上述情况更小的价值。