Phát biểu bài toán

Cho một mạng máy tính gồm ~ N ~ máy và ~ M ~ liên kết hai chiều giữa các máy. Các máy được đánh số từ ~ 1 ~ đến ~ N ~. Máy của Bờm là máy ~ 1 ~ và máy của Cuội là máy ~ N ~. Mỗi liên kết có thời gian truyền dữ liệu khác nhau. Độ dài đường truyền dữ liệu giữa hai máy bất kỳ được xác định là độ dài của đường đi ngắn nhất giữa hai máy đó.

Bờm quyết định gắn ~ K ~ thiết bị tăng tốc mạng vào một số kênh để cải thiện tốc độ truyền dữ liệu. Mỗi thiết bị tăng tốc sẽ giảm thời gian truyền trên một kênh xuống còn một nửa.

Yêu cầu: Hãy tính tốc độ kết nối tốt nhất có thể giữa máy ~ 1 ~ và máy ~ N ~ khi gắn ~ K ~ thiết bị tăng tốc một cách tối ưu.

Dữ liệu vào

1. Dòng đầu chứa ba số nguyên ~ N, M, K ~ ~(1 \leq N \leq 1000, 1 \leq M \leq 10^5, 1 \leq K \leq 10)~:

   • ~ N ~: Số lượng máy tính.
   • ~ M ~: Số lượng liên kết giữa các máy.
   • ~ K ~: Số lượng thiết bị tăng tốc.

2. ~ M ~ dòng tiếp theo, mỗi dòng chứa ba số ~ x, y, c ~:

   • ~ x, y ~: Hai máy được kết nối.
   • ~ c ~: Thời gian truyền dữ liệu giữa máy ~ x ~ và ~ y ~ ~(1 \leq c \leq 10^6)~.

Dữ liệu ra

• Một số duy nhất là thời gian truyền nhỏ nhất giữa máy ~ 1 ~ và máy ~ N ~ sau khi tối ưu việc gắn ~ K ~ thiết bị, làm tròn đến 2 chữ số thập phân.

Ví dụ minh hoạ

Input

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

Output

4.25

Giải thích:

• Nếu ta gắn thiết bị tăng tốc vào kênh ~ 2 \to 3 ~ và ~ 4 \to 5 ~, thời gian truyền trên kênh này giảm lần lượt còn ~ 9/2 = 4.5 ~ và ~ 5/2 = 2.5 ~.
• Đường đi ngắn nhất từ máy ~ 1 \to 2 \to 3 \to 5 ~ có thời gian là ~ 1 + 4.5 + 1 = 6.5 ~.
• Đường đi tốt nhất sau tối ưu là ~ 1 \to 4 \to 5 ~ với tổng thời gian ~ 4.25 ~.