Mỗi tối, Farmer John rung một chiếc chuông khổng lồ để gọi các cô bò về chuồng ăn tối. Vì mong muốn đến chuồng nhanh nhất có thể, tất cả chúng đều đi theo lộ trình ngắn nhất có thể để đến đó.

Trang trại được mô tả bởi một tập gồm \(N\) cánh đồng (\(1 \leq N \leq 10\,000\)), được đánh số thuận tiện từ \(1 \ldots N\), trong đó chuồng nằm ở cánh đồng \(1\). Các cánh đồng được nối bởi một tập gồm \(M\) đường mòn hai chiều (\(N-1 \leq M \leq 50\,000\)). Mỗi đường mòn có một thời gian di chuyển tương ứng, và từ mọi cánh đồng đều có đường đi đến chuồng qua một số đường mòn.

Cánh đồng \(i\) có \(c_i\) con bò. Khi nghe tiếng chuông báo bữa tối, tất cả những con bò này đi đến chuồng theo một lộ trình có tổng thời gian nhỏ nhất. Nếu có nhiều lộ trình cùng đạt thời gian nhỏ nhất, các cô bò chọn lộ trình "nhỏ nhất theo thứ tự từ điển" (nghĩa là khi phá vỡ thế hòa giữa hai lộ trình, chúng ưu tiên lộ trình sử dụng cánh đồng có chỉ số nhỏ hơn tại vị trí đầu tiên mà hai lộ trình khác nhau; chẳng hạn, một đường đi qua các cánh đồng \(7, 3, 6, 1\) sẽ được ưu tiên hơn một đường đi qua \(7, 5, 1\), giả sử cả hai có cùng thời gian di chuyển).

Farmer John lo ngại chuồng nằm quá xa một số cánh đồng. Ông cộng thời gian di chuyển của từng con bò trên toàn bộ đàn và gọi kết quả là tổng thời gian di chuyển. Ông muốn giảm con số này nhiều nhất có thể bằng cách thêm một đường mòn "đường tắt" có thời gian di chuyển \(T\) (\(1 \leq T \leq 10\,000\)), nối từ chuồng (cánh đồng \(1\)) đến một cánh đồng khác do ông lựa chọn. Nếu một cô bò bắt gặp đường tắt khi đang đi theo lộ trình thông thường đến chuồng, cô sẽ sử dụng nó nếu nhờ đó đến chuồng nhanh hơn. Nếu không, cô bò sẽ tiếp tục đi theo lộ trình thông thường, ngay cả khi có thể sử dụng đường tắt theo cách khác để cải thiện thời gian di chuyển.

Hãy giúp Farmer John xác định mức giảm tổng thời gian di chuyển lớn nhất có thể đạt được bằng cách thêm đường tắt.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(T\). Dòng tiếp theo chứa \(N\) số nguyên \(c_1 \ldots c_N\), mỗi số nằm trong khoảng \(0 \ldots 10\,000\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một đường mòn bằng ba số nguyên \(a\), \(b\) và \(t\), trong đó đường mòn nối hai cánh đồng \(a\), \(b\) và có thời gian di chuyển \(t\). Mọi thời gian di chuyển đều nằm trong khoảng \(1 \ldots 25\,000\).

Dữ liệu ra

In ra mức giảm tổng thời gian di chuyển lớn nhất mà Farmer John có thể đạt được.

Ví dụ

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

40

Nguồn

Đề bài gốc: USACO 2019 January Contest, Gold — Shortcut

Tác giả: Brian Dean