题目描述

你好啊，伙伴！你被任命负责这一带的邮件投递。总部位于首都，Penelope 小姐请我们把她的时髦事迹通知所有当地农庄。这里的道路经过设计，使每座农庄到首都之间都只有唯一一条道路路径，途中可能经过若干其他农庄。骑马通过每条道路都恰好需要一天。

每座农庄都希望按自己的特定时间表收到消息，以免分散雇工的注意力；如果投递早于或晚于期望日期，他们都会生气。具体而言，农庄 $i$ 希望在第 $D_i$ 天收到消息。若消息在第 $d$ 天到达，该农庄的愤怒值为

$$C_i(D_i-d)^2.$$

我们希望最小化所有农庄的愤怒值总和，因此应尽量在接近期望日期时把重要消息送到每座农庄。

唯一的问题是……我们其实一匹马也没有。作为替代，每个地点——农庄或首都——每天可以征用恰好一匹当地的马，让它载着一名骑手行驶一天，并在当天结束时自行返回出发地点。别担心，这些马认识回家的路。第二天，另一名骑手可以使用同一匹马前往另一个地点；首都和所有农庄都重复这一过程。

还有一件事：我们可不会付钱让骑手待在农庄里无所事事、惹出谁知道什么麻烦。因此，如果消息在第 $d$ 天到达农庄 $i$，并且有 $m$ 条道路通向尚未收到消息的相邻农庄，那么在第 $d+1,d+2,\ldots,d+m$ 天，每天都必须有一匹马从农庄 $i$ 出发，直到这些相邻农庄全部被访问。即使多等待几天会让某些农庄的愤怒值更低，也不允许等待。

例如，考虑图 1 中对应样例一的农庄布局，每座农庄左侧标出了 $C_i,D_i$。最优投递方案如下：

第 $1$ 天：从首都派一匹马前往农庄 $3$。
第 $2$ 天：从首都派一匹马前往农庄 $1$，同时从农庄 $3$ 派一匹马前往农庄 $7$。
第 $3$ 天：从首都派一匹马前往农庄 $2$，从农庄 $1$ 派一匹马前往农庄 $4$，并从农庄 $3$ 派一匹马前往农庄 $6$。
第 $4$ 天：从农庄 $1$ 派一匹马前往农庄 $5$。

从农庄 $1$ 到 $7$ 的愤怒值总和为

$$3(1-2)^2+3(2-3)^2+2(2-1)^2+2(4-3)^2+1(6-4)^2+3(3-3)^2+4(1-2)^2=18.$$

请计算可以达到的最小总愤怒值，好让我们知道自己会面对多大的怒火。

:::align{center} :::

输入格式

第一行包含一个正整数 $n$（$n\le 200$），表示农庄数量，编号为 $1$ 到 $n$；首都编号为 $0$。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $c,d,r$（$1\le c\le 20$，$1\le d\le n$，$0\le r\le n$），其中 $c,d$ 分别给出农庄 $i$ 的 $C_i,D_i$，$r$ 表示农庄 $i$ 与农庄 $r$ 之间有一条道路；若 $r=0$，则表示道路连接首都。

所有道路保证在任意两座农庄之间，以及每座农庄与首都之间，都形成唯一的路径。

输出格式

假设第一匹马从首都出发，并在第 $1$ 天到达第一座农庄，输出能够达到的最小总愤怒值。

7
3 1 0
3 2 0
2 2 0
2 4 1
1 6 1
3 3 3
4 1 3

18

3
5 2 2
4 1 0
6 3 1

0