Thành phố Ánh Sáng

Vương quốc Andaria vừa phát minh ra một loại công nghệ mới có thể giúp giảm chi phí đi lại trên các con đường nối các thành phố. Nhà vua muốn thử nghiệm công nghệ này trên hành trình từ thủ đô (thành phố \(1\)) đến Thành phố Ánh Sáng (thành phố \(N\)).

Vương quốc được mô hình hóa dưới dạng một đồ thị với \(N\) thành phố và \(M\) con đường. Mỗi con đường nối hai thành phố \(u\) và \(v\) có trọng số \(w\), biểu thị chi phí di chuyển trên con đường này. Đặc biệt, nhờ công nghệ giảm giá mới, nhà vua có thể sử dụng tối đa \(K\) lần giảm giá. Mỗi lần giảm giá, chi phí của một con đường bất kỳ sẽ được chia đôi (lấy phần nguyên của kết quả).

Nhiệm vụ của bạn là giúp nhà vua tính toán chi phí tối thiểu để đi từ thủ đô (thành phố \(1\)) đến Thành phố Ánh Sáng (thành phố \(N\)), với tối đa \(K\) lần sử dụng công nghệ giảm giá.

Lưu ý mỗi con đường chỉ được phép giảm giá một lần.

Input

• Dòng đầu tiên chứa ba số nguyên \(N\), \(M\), \(K\) \((2 \leq N \leq 10^5, 1 \leq M \leq 10^5, 0 \leq K \leq 7)\).
• \(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^9)\), biểu thị một con đường nối hai thành phố \(u\) và \(v\) với chi phí \(w\).

Output

• Ghi ra một số nguyên duy nhất là chi phí tối thiểu để đi từ thành phố \(1\) đến thành phố \(N\), dữ liệu của bài đảm bảo có đường đi từ \(1\) đến \(N\).

Example

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

1

7 7 0
4 5 4
1 4 5
1 2 2
1 6 1
1 3 1
4 7 5
5 6 1

10

Scoring

• \(20\%\) số điểm: \(N, M \leq 100\).
• \(30\%\) số điểm: \(K=1\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.