伙计，你好！你现在负责这一带的邮件投递工作。你的总部位于首都（Capital City），Penelope 小姐要求我们将她那些时髦的举动告知当地所有的农场。这里的道路建设方式使得每个农场都仅通过一组道路与首都相连，这组道路可能经过多个其他农场。骑马在每条道路上行驶恰好需要一天时间。

每个农场都希望在特定的时间表收到消息（以免打扰雇工工作），如果投递时间过早或过晚，他们会感到恼火。具体来说，每个农场 $i$ 都有一个接收消息的理想日期 $D_i$。如果消息在第 $d$ 天到达，该农场的愤怒值即为 $C_i(D_i - d)^2$。显然，我们希望最小化所有农场的总愤怒值，因此我们需要骑上马，尽可能在接近理想日期的时候将这些重要信息送到每个农场！唯一的问题是……嗯……我们实际上并没有马。相反，我们每天可以从每个地点（农场或首都）征用恰好一匹马，骑行 1 天，并在当天结束时让它回到出发地点（别担心，这些马知道怎么找路回去）。第二天，另一名骑手可以带上这匹马前往不同的地点（如果需要的话）。这个过程在所有农场以及首都都会重复。

还有一件事：我们可不付钱让骑手在任何农场闲坐，惹出什么乱子来。因此，如果消息在第 $d$ 天到达农场 $i$，且有 $m$ 条道路通往 $m$ 个尚未收到消息的其他农场，那么从第 $d+1, d+2, \dots, d+m$ 天开始，每天都将有一匹马从农场 $i$ 出发，直到所有相邻的城市都被访问过，即使等待额外的天数可能会降低某些农场的愤怒值。

例如，考虑图 K.1 所示的农场布局（对应样例输入 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 = 3 + 3 + 2 + 2 + 4 + 0 + 4 = 18$。

你能帮我们算出人们总共会有多愤怒，好让我们知道接下来要面对什么吗？

输入格式

输入的第一行包含一个正整数 $n$ ($n \le 200$)，表示农场的数量，编号为 1 到 $n$，首都编号为 0。接下来有 $n$ 行，每行包含三个整数 $c, d, r$ ($1 \le c \le 20, 1 \le d \le n, 0 \le r \le n$)，其中第 $i$ 行指定了第 $i$ 个农场的 $C_i$ 和 $D_i$ 值，且 $r$ 表示存在一条从农场 $i$ 到农场 $r$（若 $r=0$ 则为首都）的道路。道路的设置使得任意两个农场之间，以及每个农场与首都之间，都存在唯一的路径。

输出格式

输出在假设第一匹马从首都出发并在第 1 天到达第一个农场的情况下，所能达到的最小总愤怒值。

图 K.1：示例布局。

样例

样例输入 1

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

样例输出 1

18

样例输入 2

3
5 2 2
4 1 0
6 3 1

样例输出 2

0