Remote Training on Programming

В космической федерации имеется n населённых планет. Планеты находятся в разных звёздных системах, поэтому перелёты между ними могут занимать многие годы... К счастью, недавно правительство федерации смогло приобрести у технически более развитой цивилизации сразу два гиперпортала. Теперь для размещения порталов нужно выбрать какие-то две планеты u и v, а на каждой из остальных планет построить приёмо-передающую станцию для связи с одним из порталов. Станции устроены проще, чем порталы, поэтому федерация может построить их своими силами.

Каждая станция настраивается на работу с конкретным порталом – то есть через неё можно будет перемещаться либо только на планету u (и обратно), либо только на планету v (и обратно). Для связи планет u и v между собой дополнительных станций строить не нужно. В конечном результате от любой планеты можно будет добраться до любой другой, сделав не более трёх прыжков.

Приёмо-передающие станции делятся на три типа в зависимости от мощности:

• станция типа 1 имеет низкую мощность, строительство каждой такой станции обойдётся в один миллион межгалактических кредитов,
• станция типа 2 имеет среднюю мощность и будет стоить два миллиона кредитов;
• станция типа 3 имеет высокую мощность и будет стоить три миллиона кредитов.

Для каждой пары планет i и j известно, станцию какого типа достаточно построить на планете i для связи с порталом на планете j (в предположении, что он там будет). Определите, какую минимальную сумму придётся потратить на строительство.

3
013
302
230

1

4
0323
2033
3302
3130

3