Максимальный покрывающий лес орграфа
Задан ориентированный взвешенный граф. Требуется покрыть его набором исходящих деревьев суммарной максимальной стоимости, которые непересекаются по вершинам.
Входные данные
Входной файл состоит из одного или более наборов входных данных. Каждый набор начинается со строки, содержащей два целых числа n и m (1 ≤ n ≤ 200, 0 ≤ m ≤ 10000). n - количество вершин графа, а m - количество рёбер. Далее идёт m строк, каждая из которых содержит по три числа x_i, y_i, c_i - стартовую вершину, конечную вершину и вес дуги. Орграф не содержит петель, но может содержать кратные дуги.
Суммарное количество дуг по всем наборам входных данных одного теста не превосходит 10000.
Выходные данные
Для каждого набора входных данных выведите три строки. В первую из них выведите вес оптимального покрытия деревьями, во вторую - количество дуг в покрытии, в третью - номера выбранных в покрытие дуг. Выведите пустую строку после каждого блока выходных данных.