2459. Золотая шахта

Питер, используя современные технологии, обнаружил местонахождение нескольких золотых самородков. Чтобы до них добраться, нужно выкопать тоннели либо от входа в шахту, либо от местонахождения какого-то другого самородка. На копание тоннеля необходимо затратить некоторую сумму, которая окупается после продажи найденных самородков.

Напишите программу, которая определит максимальную прибыль Питера и минимальную сумму, которая потребуется на первоначальных этапах для добычи тех самородков, которые обеспечат эту максимальную прибыль.

Первая строка ввода содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 100`) – количество самородков. Далее следует `n` строк, каждая строка содержит три целых числа – номер самородка `p_i`, от которого нужно копать тоннель до `i`-го самородка (`0\ ≤\ p_i\ <\ i`, 0 – вход в шахту), ценность `i`-го самородка `c_i` (`1\ ≤\ c_i\ ≤\ 100`) и стоимость прокладки тоннеля `d_i` (`1\ ≤\ d_i\ ≤\ 100`).

В первой строке вывести два целых числа – максимальная прибыль Питера и минимальная сумма, которая потребуется на первоначальных этапах для получения максимальной прибыли. Если прибыль не нулевая, то во второй строке вывести количество выкопанных самородков, а в третьей строке – порядок выкапывания самородков, обеспечивающий минимум средств, привлекаемых со стороны. Если существует несколько вариантов решения, выведите любой из этих вариантов.

6
0 1 3
1 5 4
1 15 10
0 15 20
4 30 20
5 5 10

9 21
5
4 1 2 3 5

1
0 10 20

0 0