Câu chuyện xảy ra từ rất lâu, khi Trái Đất mới hình thành và IOI còn chưa có trong mơ.

Serpent sống trong một vùng đất có \(N\) hố nước, được đánh số từ \(0\) đến \(N-1\). Có \(M\) đường mòn hai chiều nối các cặp hố nước để Serpent đi dạo. Giữa mỗi cặp hố nước có nhiều nhất một dãy đường mòn kết nối chúng, trực tiếp hoặc gián tiếp; một số cặp có thể hoàn toàn không được kết nối. Do đó, \(M \le N-1\). Mỗi đường mòn có một số ngày cần thiết để Serpent đi qua, và thời gian này có thể khác nhau giữa các đường mòn.

Kangaroo, bạn của Serpent, muốn xây dựng thêm đúng \(N-M-1\) đường mòn để Serpent có thể đi lại giữa mọi cặp hố nước. Kangaroo có thể nối bất kỳ cặp hố nước nào; mỗi đường mòn mới đều cần \(L\) ngày để đi qua.

Kangaroo muốn xây dựng các đường mòn mới sao cho thời gian đi lại lớn nhất giữa hai hố nước bất kỳ là nhỏ nhất có thể. Hãy xác định thời gian lớn nhất đó sau khi xây dựng tối ưu.

Cài đặt

Bạn cần nộp một tệp cài đặt hàm C/C++ sau và phải dùng #include "dreaming.h":

int travelTime(int N, int M, int L,
        int A[], int B[], int T[]);

Dữ liệu vào

Các tham số N, M, L lần lượt là số hố nước, số đường mòn đã có và số ngày cần để đi qua mỗi đường mòn mới. Các mảng A, B, T có độ dài \(M\), mô tả các đường mòn đã có. Với \(0 \le i < M\), đường mòn có chỉ số \(i\) nối A[i] với B[i] và cần T[i] ngày để đi qua theo một trong hai chiều.

Dữ liệu ra

Hàm travelTime trả về thời gian đi lại lớn nhất giữa mọi cặp hố nước, tính bằng ngày, sau khi thêm \(N-M-1\) đường mòn để tất cả hố nước được kết nối và thời gian lớn nhất này nhỏ nhất có thể.

Ràng buộc

• Giới hạn thời gian: 1 giây.
• Giới hạn bộ nhớ: 64 MiB.
• \(1 \le N \le 100\,000\).
• \(0 \le M \le N-1\).
• \(0 \le A[i], B[i] \le N-1\) với \(0 \le i < M\).
• \(1 \le T[i] \le 10\,000\) với \(0 \le i < M\).
• \(1 \le L \le 10\,000\).

Phân nhóm

Mỗi nhóm tuân theo các ràng buộc chung và các điều kiện bổ sung sau.

Trình chấm mẫu

Trình chấm mẫu đọc tệp dreaming.in theo định dạng:

• Dòng 1: N M L.
• \(M\) dòng tiếp theo: dòng ứng với chỉ số \(i\) chứa A[i] B[i] T[i], theo thứ tự \(i=0,\ldots,M-1\).

Ví dụ

12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

18