Có \(n\) thành phố và \(m\) con đường hai chiều. Cần vận chuyển các mặt hàng thiết yếu từ thành phố \(1\) tới tất cả các thành phố khác (việc vận chuyển tới các thành phố khác luôn thực hiện được).

Mỗi con đường đều có thu phí. May mắn thay, bạn có \(k\) thẻ ưu đãi, nghĩa là khi đi từ thành phố \(1\) tới bất kỳ thành phố nào khác, bạn có thể chọn tối đa \(k\) con đường và không bị tính phí khi đi qua các con đường đó.

Hãy xác định chi phí tối thiểu để chuyển hàng tới mỗi thành phố. Lưu ý có thể xem việc vận chuyển từ thành phố \(1\) tới các thành phố khác là độc lập nhau.

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)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa \(3\) 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 nối \(u, v\) với chi phí \(w\).

Output

• In \(n\) số nguyên, số thứ \(i\) là chi phí tối thiểu để vận chuyển tới 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