Giải bóng đá TechLeague quy tụ ~N~ đội bóng, mỗi đội đặt tại một sân vận động khác nhau trong thành phố. Ban tổ chức cần tối ưu hóa lịch trình thi đấu và quãng đường di chuyển để đảm bảo thời gian nghỉ ngơi hợp lý giữa các trận đấu.

Công việc của bạn gồm ba nhiệm vụ quan trọng:

• Tìm đường đi ngắn nhất giữa mọi cặp sân vận động để xác định quãng đường di chuyển tối ưu giữa các đội.
• Tìm lịch thi đấu tối ưu nhất sao cho tổng quãng đường di chuyển giữa các trận đấu là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \le N \le 10, 1 \le M \le 10^4~).
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, w~ (~1 \le u, v \le N, 0 \le w \le 10^6~), biểu thị một tuyến đường nối giữa hai sân vận động ~u~ và ~v~ với chiều dài là ~w~ (km).

Nếu không có tuyến đường trực tiếp giữa hai sân vận động, mặc định quãng đường là ~10^9~.

Output

• ~N~ dòng đầu tiên, mỗi dòng ghi ~N~ số nguyên biểu thị khoảng cách ngắn nhất giữa các sân vận động.
• Dòng thứ ~N+1~ ghi lịch thi đấu tối ưu nhất (hoán vị của ~1, 2, ..., N~). Nếu có nhiều lịch tối ưu, thì đưa ra hoán vị có thứ tự từ điển lớn nhất.
• Dòng thứ ~N+2~ đưa ra giá trị tổng quãng đường di chuyển nhỏ nhất tìm được.

Sample Input 1

3 3
1 2 5
2 3 10
1 3 3

Sample Output 1

0 5 3
5 0 8
3 8 0
3 1 2
8

Giải thích

Lịch thi đấu tối ưu: ~3 \to 1 \to 2~. Tổng quãng đường di chuyển: ~8~.

Subtasks