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).

Nhưng mọi con đường đều có thu phí. May mắn thay, bạn có \(k\) thẻ ưu đãi, có 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 \(k\) con đường đó.

Bạn cần xác định chi phí tối thiểu để có thể chuyển hàng tới mỗi thành phố. Lưu ý bạn có thể xem việc vận chuyển hàng hóa 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 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ả \(1\) con đường nối \(2\) thành phố \(u, v\) với chi phí \(w\) để đi qua.

Output

• Gồm \(n\) số nguyên, số thứ \(i\) ứng với chi phí tối thiểu vớ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

Nguồn: CĐ DHBB Chuyên Hạ Long