Trong khi nhờ các bạn giải giùm bài của cô kieulqd đưa.Thì TV lại chiếu về 1 vụ bạo loạn gồm k kẻ phản diện đang tập trung tại thành phố nào đấy.Nhờ công nghệ mới của cô, Bob152 đã mã hóa thành công cả thành phố New Nhơn Quy thành 1 đồ thị vô hướng gồm ~n~ đỉnh đánh số từ ~1~ ~->~ ~n~ , đỉnh thứ ~n~ là đỉnh mà bọn ác nhân đang múa quạt tán gẫu và có ~m~ con đường nối giữa hai đỉnh ~u~ và ~v~ và có độ dài là ~w~.Tới công chuyện , Bob152 khoác lên mình bộ suit mới nhưng cái máy bắn tơ thì chẳng mới tí nào. Cứ mỗi khi đấm xong 1 kẻ xấu thì máy bắn tơ bằng một lý do nào đấy mà nó chỉ đủ tơ để spider quay về nhà mình (là đỉnh 1 ) và reload lại máy bắn tơ.Vì spiderman Bob152 là 1 người rất điêu và kiêu ngạo nên anh ta sẽ chọn đường đi từ nhà mình đến chỗ đấm nhau mỗi lần sạc lại và bay đi thì spiderman sẽ đi đường đi ngắn nhất nhưng sẽ không đi một con đường mà trước đó đã đi rồi.

Ví dụ :

Nếu Bob parker đã đi đường :

~1 -> 2 -> 3 -> 4~

~1 -> 3 ->2 -> 4~

Thì lần tiếp theo anh ta không thể đi được những đường ở trên :

~1 -> 2 -> 3 ->2 -> 4~ :Hợp lệ

~1 -> 3 - > 2 ->4~ : Không hợp lệ

Anh ta cũng không thể đến nơi rồi quay lại 1 đỉnh khác khi đã ở đỉnh ~n~.

Giả sử ~n~ = 5

~1- >2 -> 3 -> 4 -> 5~ : Hợp lệ

~1 -> 2 -> 3 -> 4 ->5 -> 4 -> 5 ~ : Không hợp lệ

~1 - > 2 -> 1 -> 3 -> 2 -> 4 -> 5 ~ : Hợp lệ

Mục đích của việc chọn mỗi con đường khác nhau là 1 cách khác để múa quạt gây suy yếu tinh thần của những kẻ phản diện.Vì thế , Bob152 nhờ các bạn tính toán tổng độ dài đường đi ngắn nhất mà Bob152 phải đi để dọn hết đống kẻ thù.Vì cộng đồng Phờ-ri-phai chúng ta , các bạn hãy viết chương trình giúp Bob152 để anh ta chuẩn bị tơ và đấm mồm bọn phản diện.

Input :

Dòng đầu tiên chứa 3 số ~k~ , ~n~ , ~m~ biểu thị cho ~n~ đỉnh và ~m~ cạnh trong đồ thị và ~k~ kẻ thù.

~m~ dòng tiếp theo mỗi dòng chứa 3 số nguyên ~u_i~ , ~v_i~ , ~w_i~ , có 1 cạnh nối hai đỉnh ~u_i~ và ~v_i~ và có trọng số là ~w_i~.

Output :

Dòng đầu tiên chứa tổng quãng đường mà spidey phải đi.

Từ dòng 1 -> ~k~

Dòng thứ ~i~ chứa đường đi ngắn nhất của spidey khi đi lần thứ ~i~.

Example Input:

4 5 8
1 2 1
1 3 2
1 4 2
2 3 2
2 5 3
3 4 3
3 5 4
4 5 6

Example output:

23
4
6
6
7

Giải thích test đề:

Các đường đi ngắn nhất :

~1. 1 -> 2 - > 5~

~2.1 - > 3 -> 5~

~3.1 -> 2 -> 1 ->2 -> 5~

~4.1-> 3 -> 2 -> 5~

Giới hạn : ~4~ ~\leq~ ~ n~ ~\leq~ ~800~ , ~1~ ~\leq~ ~m~ ~\leq~ ~4000 ~, ~0~ ~\leq~ ~w_i~ ~\leq~ ~9500~ ,~K~ ~\leq~ ~800~.

Subtask 1 : ~n~ ~\leq~ ~10~; (7 %)

Subtask 2 : ~K~ ~=~ ~1~ (8 %)

Subtask 3 : ~K =1~ và ~w_i~ ~= 1~ (15 %)

Subtask 4 : ~w_i~ = 1 (25 %)

Subtask 5 : Không ràng buộc gì thêm (45 %)