Sứ mệnh tiếp tế

Thành phố Syrjälä đang phải đối mặt với một cuộc khủng hoảng lớn! Nguồn cung cấp hàng hóa thiết yếu từ thủ đô đã bị gián đoạn, và bạn---một nhà điều phối tài ba---có nhiệm vụ đảm bảo tất cả các thành phố khác trong vương quốc nhận được hàng hóa một cách nhanh nhất và tiết kiệm nhất.

Tuy nhiên, việc vận chuyển không hề miễn phí! Mỗi con đường giữa các thành phố đều thu phí, và bạn phải tính toán cẩn thận để chi phí vận chuyển là thấp nhất.

May mắn thay, vua của Syrjälä đã cấp cho bạn \(k\) thẻ miễn phí đặc biệt. Khi sử dụng một thẻ, bạn có thể đi qua một con đường bất kỳ mà không mất phí. Bạn có thể sử dụng tối đa \(k\) thẻ trên mỗi tuyến đường từ thủ đô đến một thành phố khác, nhưng không thể sử dụng nhiều lần trên cùng một con đường.

Hãy tìm cách vận chuyển hàng hóa từ Syrjälä (thành phố 1) đến tất cả các thành phố khác với chi phí nhỏ nhất có thể!

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) \((1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^5, 1 \leq k \leq 18)\) --- số lượng thành phố, số con đường hai chiều, và số thẻ miễn phí có thể sử dụng.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) \((1 \leq u, v \leq n, 1 \leq w \leq 10^6)\), mô tả một con đường hai chiều giữa thành phố \(u\) và thành phố \(v\) với chi phí đi qua là \(w\). Dữ liệu đảm bảo luôn có đường đi giữa các cặp đỉnh.

Output

Gồm \(n\) số nguyên, số thứ \(i\) tương ứng với chi phí tối thiểu để vận chuyển hàng hóa từ thành phố 1 đến thành phố \(i\).

Example

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

0 0 0 2 2