Розріз

Знайдіть мінімальний розріз між вершинами 1 і n у заданому неорієнтовному графі.

Вхідні дані

У першому рядку вхідного файлу міститься n (1 ≤ n ≤ 100) – число вершин у графі і m – кількість ребер. У наступних m рядках вхідного файлу міститься опис ребер. Ребро задано номерами вершин, які воно з'єднує, і його пропускною здатністю (додатне ціле число, яке не перевищує десять мільйонів), при цьому ніякі дві вершини не з'єднується більш ніж одним сегментом.

Вихідні дані

У першому рядку вихідного файлу повинні міститись кількість ребер у мінімальному розрізі і їх сумарна пропускна здатність. У наступному рядку виведіть зростаючу послідовність номерів ребер (ребра нумеруються у тому порядку, у якому вони були задані у вхідному файлі).

Приклади