Farmer John kiểm tra những chú bò của mình mỗi ngày. Anh ta đi trên một số đường trong ~M~ ~(1 \leq M \leq 50000)~ đường mòn được đánh số từ ~1~ đến ~M~ bắt đầu từ bãi cỏ ~1~ và đi đến bãi cỏ ~N~ (dữ liệu đầu vào luôn đảm bảo tồn tại một đường đi như vậy). ~N~ ~(1 \leq N \leq 10000)~ bãi cỏ được đánh số liên tiếp ~1~...~N~ trong trang trại của Farmer John được nối bằng những đường mòn hai chiều. Đường mòn ~i~ nối bãi cỏ ~P1_i~ và ~P2_i~ ~(1 \leq P1_i , P2_i \leq N)~ và yêu cầu ~T_i~ ~(1 \leq T_i \leq 10^6)~ đơn vị thời gian để đi qua.

Anh ta muốn sửa lại một số đường mòn trong trang trại để tiết kiệm thời gian trong hành trình của anh ta. Cụ thể, anh ta sẽ chọn ~K~ ~(1 \leq K \leq 20)~ đường mòn để sửa thành đường cao tốc, thời gian trên những đường này sẽ giảm xuống ~0~. Hãy giúp Farmer John chọn những đường mòn để tối thiểu thời gian đi từ bãi cỏ ~1~ đến bãi cỏ ~N~.

Input

• Dòng ~1~: Ba số nguyên cách nhau bởi dấu cách: ~N~, ~M~ và ~K~

• Dòng ~2~...~M+1~: Dòng ~i+1~ miêu tả đường mòn ~i~ với ba số nguyên cách nhau bởi dấu cách: ~P1_i~, ~P2_i~ và ~T_i~

Output

• Dòng ~1~: Chiều dài của đường đi ngắn nhất từ bãi cỏ ~1~ đến bãi cỏ ~N~ sau khi sửa không nhiều hơn ~K~ đường mòn.

Sample Input

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Sample Output

1