Giải bài trực tuyến

Cho một đa đồ thị vô hướng N đỉnh, M cạnh, mỗi cạnh có 1 trọng số nguyên dương.

Yêu cầu: Hãy chọn ra một số cạnh sao cho đồ thị tạo bởi N đỉnh và các cạnh được chọn này đảm bảo liên thông giữa 3 đỉnh 1, 2, 3 và tổng trọng số của các cạnh được chọn là nhỏ nhất. Dữ liệu vào đảm bảo có phương án.

Giới hạn

• 3 ≤ N ≤ 100
• 4 ≤ M ≤ 20000
• Trọng số 1 cạnh ≤ 10000

Input

• Dòng đầu tiên gồm 2 số nguyên: N, M.
• M dòng tiếp theo: dòng thứ i gồm 3 số nguyên dương U V C tương ứng là cạnh này nối liền đỉnh U với đỉnh V, trọng số là C.

Output

• Dòng 1: Chi phí nhỏ nhất.
• Dòng 2: Số nguyên K là số cạnh chọn ra.
• Ghi ra K số là chỉ số các cạnh đã chọn, các số ghi cách nhau ít nhất một dấu cách.

Example

Input:
3 4
1 2 1
2 3 4
1 3 2
1 2 3

Output:
3
2
1 3