Công viên JOI có \(N\) quảng trường và \(M\) đường hai chiều. Đường \(i\) nối \(A_i,B_i\), dài \(D_i\); đồ thị liên thông. Khoảng cách giữa hai quảng trường là tổng độ dài nhỏ nhất của một đường đi.

Kế hoạch cải tạo chọn số nguyên \(X\ge0\), nối ngầm lẫn nhau mọi quảng trường cách quảng trường 1 không quá \(X\), với chi phí \(CX\). Sau đó xóa miễn phí mọi đường có cả hai đầu đã được nối ngầm, rồi sửa tất cả đường còn lại; sửa đường dài \(d\) tốn \(d\). Ban đầu không có đường ngầm. Hãy tìm tổng chi phí nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa \(N,M,C\). Mỗi trong \(M\) dòng sau chứa \(A_i,B_i,D_i\).

Dữ liệu ra

In tổng chi phí nhỏ nhất.

Ràng buộc

Không có hai đường nối cùng một cặp quảng trường (kể cả đảo thứ tự), và đồ thị liên thông.

Phân nhóm

• Nhóm 1 (15 điểm): \(N\le100\), \(M\le200\), \(C\le100\), \(D_i\le10\).
• Nhóm 2 (45 điểm): \(N\le100\), \(M\le4000\).
• Nhóm 3 (40 điểm): không có ràng buộc bổ sung.

Ví dụ

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

14

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

15

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

10