Mô tả bài toán: Tìm k đường bay ngắn nhất

Nhiệm vụ của bạn là tìm k đường bay ngắn nhất từ thành phố Syrjälä (thành phố 1) đến thành phố Metsälä (thành phố ~n~). Một đường bay có thể đi qua cùng một thành phố nhiều lần.

Lưu ý: Có thể có nhiều đường bay với cùng giá tiền, và tất cả các đường đó đều cần được xem xét.

Input:

• Dòng đầu tiên chứa ba số nguyên n, m, và k:
  • ~n~: số thành phố.
  • ~m~: số chuyến bay.
  • ~k~: số đường bay ngắn nhất cần tìm.
• Tiếp theo có m dòng, mỗi dòng chứa ba số nguyên a, b, và c:
  • ~a~: thành phố bắt đầu của chuyến bay.
  • ~b~: thành phố đích của chuyến bay.
  • ~c~: giá của chuyến bay từ ~a~ đến ~b~.

Bạn có thể giả định rằng có ít nhất ~k~ đường bay khác nhau từ Syrjälä đến Metsälä.

Output:

• In ra ~k~ số nguyên: giá của ~k~ đường bay ngắn nhất từ Syrjälä đến Metsälä, theo thứ tự tăng dần.

Ràng buộc:

• ~2 \leq n \leq 10^5~
• ~1 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a, b \leq n~
• ~1 \leq c \leq 10^9~
• ~1 \leq k \leq 10~

Ví dụ :

Input:

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

Output:

4 4 7

Giải thích:

• Các đường bay ngắn nhất:
  • ~1 \rightarrow 3 \rightarrow 4~: giá ~4~.
  • ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~: giá ~4~.
  • ~1 \rightarrow 2 \rightarrow 4~: giá ~7~.