Məsələlər
Разрез
Разрез
Найдите минимальный разрез между вершинами \textbf{1} и \textbf{n} в заданном неориентированном графе.
\InputFile
На первой строке входного файла содержится \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}) -- число вершин в графе и \textbf{m} -- количество ребер. На следующих \textbf{m} строках входного файла содержится описание ребер. Ребро описывается номерами вершин, которые оно соединяет, и его пропускной способностью (положительное целое число, не превосходящее десять миллионов), при этом никакие две вершины не соединяются более чем одним сегментом.
\OutputFile
На первой строке выходного файла должны содержаться количество ребер в минимальном разрезе и их суммарная пропускная способность. На следующей строке выведите возрастающую последовательность номеров ребер (ребра нумеруются в том порядке, в каком они были заданы во входном файле).
Giriş verilənləri #1
6 8 1 2 3 1 3 3 2 4 2 2 5 2 3 4 2 3 5 2 5 6 3 4 6 3
Çıxış verilənləri #1
2 6 1 2