该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

争者留其名

题目背景

争者留其名。

题目描述

给定一个 $n$ 个点的树，点的编号为 $1 \sim n$，边的编号为 $1 \sim n - 1$。第 $i$ 条边连接 $u_i$ 和 $v_i$，长度为 $w_i$。每个点有个 01 权值 $c_i$。

现在你可以至多进行一次下面操作：选择两个点 $u,v$，交换 $c_u, c_v$ 的值。

记 $\operatorname{dis}(u,v)$ 表示树上两点 $u$ 和 $v$ 之间的距离，距离定义为连接它们的唯一简单路径中边的长度之和。

接下来依次进行下面的操作：

1. 定义一个变量 $r=0$。
2. 选择两个不同的点 $u, v$，使得 $c_u=c_v=1$，若无法选出则结束。
3. 令 $c_u=c_v=0$，令 $r$ 加上 $\operatorname{dis}(u,v)$。
4. 回到第 2 步。

你希望通过选择合适的操作（包括初始时的交换 $c_u, c_v$ 的操作，以及选择 $u, v$ 令 $r$ 增加 $\operatorname{dis}(u,v)$ 的操作）以最小化结束时的 $r$，求出 $r$ 可能的最小值。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个非负整数 $c_1, \ldots, c_n$，表示每个点的权值。

接下来 $n-1$ 行，第 $i$ 行三个正整数 $u_i,v_i,w_i$，表示第 $i$ 条边。

输出格式

输出一行，一个整数 $r$。

输入输出样例 #1

输入 #1

8
1 0 0 0 1 1 1 1
1 2 4
1 3 3
2 4 2
2 5 1
3 6 1
3 7 2
4 8 1

输出 #1

4

说明/提示

【样例解释 #1】

一种可能的操作方式是：

首先一次操作选择 $u=8, v=2$，交换 $c_u,c_v$，目前 $c$ 为 $1$ 的位置有 $1,2,5,6,7$。

接下来，$r=0$：

1. 选择 $u=2,v=5$，$\operatorname{dis}(2,5)=1$，$r$ 变为 $1$。
2. 选择 $u=6,v=7$，$\operatorname{dis}(6,7)=3$，$r$ 变为 $4$。
3. 无法继续选出两个位置 $u,v$ 满足 $u\ne v$ 且 $c_u=c_v=1$，操作结束。

最终答案 $r=4$，可以证明没有更小的答案。

【数据范围】 本题共 $20$ 个测试点，每个 $5$ 分。

对于所有数据，保证：

• $2 \leq n \leq 10^5$；
• $1 \leq w_i \leq 10^9$；
• $c_i \in \{0, 1\}$；
• $1 \leq u_i, v_i \leq n$；
• 保证输入的边构成一棵树。

::cute-table{tuack}

• 特殊性质：保证 $\sum_{i=1}^n c_i$ 为偶数。