Vùng đất X có N thành phố (3

-          Thành phố xuất phát là thành phố 1 và kết thúc là thành phố N.

-          Mỗi đội thi đấu có K người dự thi. Khi người thứ nhất đến được thành phố N thì người thứ hai mới bắt đầu rời khỏi thành phố 1, khi người thứ 2 đến thành được thành phố N thì người thứ 3 mới rời khỏi thành phố 1, cứ như vậy cho đến khi người thứ K về tới đích thì được xem như thời điểm tính cho toàn đội.

-          Đường chạy của các đội viên không được giống nhau hoàn toàn.

-          Có thể chạy lại đoạn đường đã chạy.

Hãy viết chương trình tính thời gian nhỏ nhất để một đội hoàng thành cuộc chạy đua tiếp sức nếu trên nếu các vận động viên có tốc độ chạy như nhau.

Input:

-          Dòng đầu ghi 2 số nguyên dương K, N và M.

-          M dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, w thể hiện một đường đi trực tiếp giữa hai thành phố i và j mất thời gian chạy là w.

Output:

-          Dòng thứ nhất chứa một số nguyên duy nhất là thời gian chạy nhỏ nhất của 1 đội

-          K dòng tiếp theo, mỗi dòng thể hiện hành trình chạy của một vận động viên trong đội là dãy các thành phố liên tiếp trên hành trình đó.