Exemplo

Entrada

6
10 2 10
5 3 15
4 5 20
20 3 5
10 1 25
15 4 15
0

Saída

Instancia #1 -- Qualidade total: 3050
5 2 1 3 6 4