Hôm nay là chủ nhật, shiba quyết định ra đảo chơi.

Quần đảo nơi shiba chơi có tất cả \(n\) đảo, được nối với nhau bằng \(m\) con đường một chiều. shiba quyết định sẽ đi tham quan từ đảo \(1\) tới đảo \(n\). Con đường thứ \(i\) nối hai đảo \(u_i\) và \(v_i\) với nhau có chi phí là \(c_i\). shiba có siêu năng lực là cải tạo các con đường (yep, ngay lập tức) tuy nhiên khả năng này chỉ có thể sử dụng \(k\) lần. Sau khi cải tạo, chi phí của con đường sẽ là \(\lfloor \frac{c_i}{2} \rfloor\). Tuy nhiên có một giới hạn là nếu như cậu ấy cải tạo ít nhất một con đường đến đỉnh thứ \(u\), thì cậu ấy sẽ không thể cải tạo bất cứ con đường nào đi ra từ đỉnh \(u\) đó.

Yêu cầu: Tìm đường đi ngắn nhất từ đảo \(1\) tới đảo \(n\). Nếu không thể tìm thấy đường đi, in ra -1.

Input

• Dòng thứ nhất chứa ba số nguyên dương \(n,m,k\) (\(n \le 10^3, m \le 10^5, k \le min(m,500)\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương \(u,v,c\) (\(u,v \le n, c \le 10^9\)).

Output

• Một số nguyên duy nhất là kết quả bài toán.

Example

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

3