이름 없는 포니 익스프레스

하우디, 파트너! 당신은 이 일대의 우편 배달 책임자로 임명되었습니다. 본부는 수도에 있고, 페넬로페 아가씨가 이 지역의 모든 농장에 그녀의 최신 소식을 전해 달라고 부탁했습니다. 이 일대의 도로는 각 농장에서 수도까지 이어지는 길이 하나뿐이고, 그 길은 다른 농장들을 거칠 수 있도록 건설되어 있습니다. 말을 타고 도로 하나를 지나는 데는 정확히 하루가 걸립니다.

각 농장은 일꾼들의 일을 방해하지 않도록 자기만의 일정에 맞춰 소식을 받기를 원합니다. 소식이 원하는 날짜보다 일찍 오거나 늦게 오면 농장은 화를 냅니다. 구체적으로, 농장 $i$에는 소식을 받기에 가장 알맞은 날 $D_i$가 있습니다. 소식이 $d$일에 도착하면 그 농장의 분노 수준은 $C_i(D_i - d)^2$입니다. 우리는 모든 농장의 분노 수준 합을 최소로 만들고 싶으므로, 각 농장에 원하는 날짜에 최대한 가깝게 소식을 전해야 합니다. 문제는 말이 없다는 것입니다. 대신 매일 각 지점(농장 또는 수도)에서 말을 정확히 한 마리씩 징발하여 하루 동안 타고, 그날이 끝나면 출발 지점으로 되돌려 보낼 수 있습니다. 말은 돌아가는 길을 알고 있으니 걱정하지 않아도 됩니다. 다음 날에는 다른 기수가 그 말을 타고 필요하면 다른 지점으로 갈 수 있습니다. 이 과정은 모든 농장과 수도에서 반복됩니다.

한 가지 더 있습니다. 기수들이 농장에서 놀고 있으면 무슨 사고를 칠지 모르므로, 대기시키는 데는 돈을 지불하지 않습니다. 따라서 농장 $i$에 $d$일에 소식이 도착했고, 아직 소식을 받지 못한 농장으로 이어지는 도로가 $m$개 있다면, 이웃한 모든 도시를 방문할 때까지 $d+1, d+2, \ldots, d+m$일마다 농장 $i$에서 말이 한 마리씩 출발합니다. 기다리면 일부 농장의 분노 수준이 낮아지더라도 이 규칙은 그대로입니다.

예를 들어, 그림 K.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$입니다.

그림 K.1: 배치 예시.

사람들이 전체적으로 얼마나 화를 낼지 계산해 주실 수 있나요? 그래야 무엇을 감당해야 할지 알 수 있습니다.

첫 줄에 농장의 수를 나타내는 양의 정수 $n$ ($n \leq 200$)이 주어집니다. 농장은 1번부터 $n$번까지 번호가 매겨지고, 수도는 0번입니다. 이어서 $n$개의 줄에 세 정수 $c$, $d$, $r$ ($1 \leq c \leq 20$, $1 \leq d \leq n$, $0 \leq r \leq n$)이 주어집니다. $i$번째 줄은 농장 $i$의 $C_i$와 $D_i$ 값이며, $r$은 농장 $i$에서 농장 $r$로 가는 도로가 있다는 뜻입니다($r$이 0이면 수도로 가는 도로). 도로는 어떤 두 농장 사이, 그리고 각 농장과 수도 사이에 경로가 정확히 하나만 존재하도록 놓여 있습니다.

첫 번째 말이 수도를 출발해 1일에 첫 번째 농장에 도착한다고 가정할 때, 달성할 수 있는 최소 분노 수준을 출력합니다.