Задача №3359. Паросочетание
Дан двудольный граф, в каждой из долей которого \(N\) вершин. В нем также есть \(M\) ребер, каждое из которых имеет свою стоимость. Требуется найти паросочетание максимальной стоимости.
В первой строке входного файла заданы числа \(1 \leq N \leq 50\) и \(1 \leq M \leq 1000\). В следующих \(M\) строках заданы ребра графа – в каждой по три числа. Первые два из них задают соответственно номера вершин в левой и правой долях, третье – стоимость. Все стоимости не превосходят 10. Гарантируется, что у каждых двух ребер есть отличие хотя бы в одном из концов.
В первой строке выходного файла выведите максимальную стоимость. В следующей строке выведите \(N\) чисел, i-ое из которых обозначает номер вершины из правой доли, с которой соединена i-ая вершина левой доли. Если i-ая вершина не соединена ни с какой вершиной правой доли, то на i-ом месте должна стоять -1. Из всех возможных ответов нужно вывести наименьший лексикографически. Один ответ считается лексикографически меньшим другого, если первое число, в котором они отличаются у него меньше.
3 5 1 1 1 2 2 1 3 3 1 2 1 2 3 2 2
4 -1 1 2