通知下发

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

题目描述

抗击疫情期间，听课不停学，通知都由各级组织向下传达。例如，校长办公室做出某项决定，先传达到各学院，学院负责人再下发到各年级，再由辅导员通知各班班长，再由班长通知到个人。

已知每个人传达到下属所消耗的时间和每个人理解信息的时间。（传达给不同的下属，时间不一定相同）

现在有一个信息要传达给一个指定者。只有信息接收者才需要理解信息（花费 $a_i$ 的时间），中间层级只起到复读机的作用，不需要花费理解信息的时间。

桐姐需要掌握这个信息传递过程的效率，于是她想找出最大时间消耗的那个路线（包括信息接收指定者所需要理解信息的时间），这样就能方便整改。

第一行一个正整数 $n$ ，代表学校的人数（校长是 $1$ 号，其他人标记为 $2$ 号到 $n$ 号）。( $1 \leq n \leq 200\,000$ )

第二行有 $n-1$ 个正整数 $a_i$ ，代表从 $2$ 号到 $n$ 号，每个人需要理解信息的时间。( $1 \leq a_i \leq 100$ )

接下来的 $n-1$ 行，每行有 $3$ 个正整数 $x,y,k$ ，代表 $x$ 是 $y$ 的上级， $x$ 向 $y$ 传播信息需要消耗 $k$ 的时间。( $1 \leq x,y \leq n,1 \leq k \leq 100$ )

一个正整数，代表桐姐选定某人作为信息接收指定者后，花费总时间的最大值。

示例1

复制

复制

若 $3$ 号为信息接受者，消耗时间为 $2+4=6$ 。

若 $2$ 号为信息接受者，消耗时间为 $4+3=7$ 。

故最大值为 $7$ 。

只有信息接收者需要理解信息，传达者不需要花费时间理解信息。