题目背景

zsh 正在 Minecraft 世界流浪！

他来到了一个神奇的、由许许多多村庄组成的神秘王国。这里的村庄与村庄之间存在着从属关系，村庄之间经济交流繁盛。

上次他已经了解了这些村庄之间的贸易情况。现在，这些村庄中的村民想要委托他帮忙把一部分道路改造成冰船高速公路，从而方便不同村庄之间的村民相互贸易。作为回报，每个村庄的村民都会根据实际情况给 zsh 一些绿宝石。

zsh 当然想要赚绿宝石，而且他想要赚取尽可能多的绿宝石。但是，这个王国实在是过于庞大，村庄数量非常多，zsh 自己计算不出应该改造哪些道路才能使赚到的绿宝石最多。所以，他又找到了你来帮忙。

题目描述

这个王国里共有 $n$ 个村庄，每个村庄的编号分别为 $1\sim n$。除了最核心的村庄（也就是王国的国都所在地），每个村庄都有且仅有 $1$ 个上属村庄。上属村庄与下属村庄之间有 $1$ 条双向道路相连。

zsh 需要挑选其中的一些道路（数量不限，可以为 $0$），把它们改造成冰船高速公路。但是，道路的改造有一个原则：对于被改造道路直接连接的所有村庄，这些村庄之间必须可以只通过冰船高速公路相互连通。对于连接村庄 $u$ 和村庄 $v$ 的道路，改造它需要花费 $c_{u,v}$ 颗绿宝石（村民并不会给 zsh 报销这些花费）。

对于任意一个村庄 $v$，该村庄的村民会根据他们村庄所直接连接的冰船高速公路数量给予 zsh 一些回报。具体地，若该村庄直接连接的冰船高速公路数量为 $d$（$0\le d\le deg_{v}$，$deg_{v}$ 表示村庄 $v$ 原本直接连接的道路数量），则他们会给出 $F_{v}\left(d\right)$ 颗绿宝石（$F_{v}\left(d\right)$ 不一定随 $d$ 的增大而增大，且不一定为正）。真是奸商！

现在 zsh 想知道，他获得的利润（即获得的回报减去改造道路的花费）最多可以为多少颗绿宝石。

输入格式

输入第 $1$ 行有 $1$ 个整数 $n$。

接下来 $n-1$ 行，每行有 $3$ 个整数 $u,v,c_{u,v}$，表示村庄 $u$ 与村庄 $v$ 之间存在一条双向道路，改造此道路的花费为 $c_{u,v}$ 颗绿宝石。

接下来 $n$ 行，第 $v$ 行有 $deg_{v}+1$ 个整数，依次表示 $F_{v}\left(0\right),F_{v}\left(1\right),\cdots,F_{v}\left(deg_{v}\right)$。

输出格式

输出 $1$ 行 $1$ 个整数，表示 zsh 可以获得的最大利润。

样例

3
1 2 2
2 3 1
0 5
0 3 7
0 4

13

3
2 1 11
3 1 7
12 15 0
1 16
7 12

27

说明/提示

【样例解释 #1】

选择 $\left(1,2\right),\left(2,3\right)$ 两条道路。改造的花费为 $2+1=3$ 颗绿宝石。此时村庄 $1,2,3$ 直接连接的冰船高速公路数量分别为 $1,2,1$，村民给出的回报为 $5+7+4=16$ 颗绿宝石。所以利润为 $16-3=13$ 颗绿宝石。

【样例解释 #2】

仅选择 $\left(2,1\right)$ 这条道路。改造的花费为 $11$ 颗绿宝石。此时村庄 $1,2,3$ 直接连接的冰船高速公路数量分别为 $1,1,0$，村民给出的回报为 $15+16+7=38$ 颗绿宝石。所以利润为 $38-11=27$ 颗绿宝石。

【样例 #3】

见附件下的 样例.zip/test3.in 与 样例.zip/test3.ans。
该样例满足测试点 $4\sim 7$ 的约束条件。

【样例 #4】

见附件下的 样例.zip/test4.in 与 样例.zip/test4.ans。
该样例满足测试点 $8\sim 11$ 的约束条件。

【样例 #5】

见附件下的 样例.zip/test5.in 与 样例.zip/test5.ans。
该样例满足测试点 $12\sim 14$ 的约束条件。

【样例 #6】

见附件下的 样例.zip/test6.in 与 样例.zip/test6.ans。
该样例满足测试点 $15\sim 17$ 的约束条件。

【样例 #7】

见附件下的 样例.zip/test7.in 与 样例.zip/test7.ans。
该样例满足测试点 $18\sim 20$ 的约束条件。

【样例 #8】

见附件下的 样例.zip/test8.in 与 样例.zip/test8.ans。
该样例满足测试点 $21\sim 25$ 的约束条件。

【数据范围与约束】

特殊性质 A：保证任意一个村庄最多只有一个直接相连的下属村庄。

特殊性质 B：保证有且仅有一个村庄有 $n-1$ 个直接相连的下属村庄。

特殊性质 C：保证对于任意一个村庄 $v$，存在整数 $a_{v},b_{v}$，使得 $F_{v}\left(d\right)=a_{v}d+b_{v}$ 对所有 $0\le d\le deg_{v}$ 成立。

特殊性质 D：保证任意一个村庄最多只有 $3$ 个直接相连的村庄（包括上属村庄和下属村庄）。

对于 $100\%$ 的数据，满足 $1\le n\le 10^{5},0\le c_{u,v}\le 10^{9},\left|F_{v}\left(d\right)\right|\le 10^{9}$。