Ở ICTU thiết kế mạng lưới điện thoại gồm N máy và M liên kết 2 chiều giữa các máy. Các máy được đánh số từ 1 đến N. Máy của An sử dụng để gọi cho Bình là máy số 1, còn máy của Bình là máy N. Mỗi đường nối cần tốn một giá trị thời gian khác nhau để truyền dữ liệu qua. Tốc độ kết nối giữa 2 máy của cặp đôi này là độ dài đường truyền dữ liệu ngắn nhất giữa hai máy đó. Vùng đất ICTU tuy giàu có và trù phú nhưng tốc độ kết nối của mạng lại khá chậm khiến cho An và Bình không thể liên lạc được, do đó An phải chạy sang nhà ông Trí để mua K thiết bị tăng tốc mạng. Thiết bị tăng tốc mạng được gắn vào các đường truyền dữ liệu giữa hai máy. Mỗi thiết bị sẽ làm giảm thời gian truyền dữ liệu của đường truyền đi một nửa.

Hãy giúp An đặt các thiết bị tăng tốc sao cho tốc độ kết nối giữa máy của An và Bình là nhanh nhất có thể để 2 bạn có thể gọi điện cho nhau mà không bị lag!

Dữ liệu:

• Dòng đầu chứa 3 số nguyên \(N, M, K (1 <= N <= 10^5; 1 <= M <= 10^5; 1 <= K <= 15)\)
• M dòng tiếp theo, mỗi dòng chứa 2 số nguyên u, v và 1 số thực w mô tả một đường truyền dữ liệu: u, v là số hiệu của 2 máy tính, w là thời gian truyền dữ liệu \((1 <= w <= 10^6)\)

Kết quả:

• In ra 1 số duy nhất là tốc độ kết nối nhanh nhất có thể sau khi đã lắp đặt các thiết bị tăng tốc, làm tròn đến 2 chữ số thập phân.

Ví dụ:

Input:

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

Output:

4.25