Задача King and Roads

Даны пары чисел(упррядоченные), каждое от 1 до n. Всего m штук. У каждой пары есть стоимость.

Надо выбрать сколько-нибудь пар чисел, так, чтобы :

Для каждого числа i от 1 до n должна существовать выбранная пара, такая что ее левое (правое) число равно i;

Тоесть все левые числа покрывают множество 1..n и тоже с правыми.

Надо минимизировать сумму всех выбранных пар.

n < 300; m < 300 * 300;