Happyland có \(N\) thị trấn, đánh số từ \(1\) đến \(N\), ban đầu được nối bởi \(M\) con đường hai chiều. Thị trấn \(1\) là trung tâm và có thể đi từ đó đến mọi thị trấn khác. Đường cũ thứ \(i\) thu phí \(c_i\) xu; mọi \(c_i\) đôi một khác nhau.

Gần đây có thêm \(K\) con đường mới do tỷ phú Greedy sở hữu. Ông được tự chọn phí cho các đường mới, các mức phí này không nhất thiết khác nhau.

Trong lễ hội sắp tới, có \(p_j\) người đi từ thị trấn \(j\) về thị trấn \(1\). Theo truyền thống, Greedy phải chọn một tập đường có tổng phí nhỏ nhất nhưng vẫn nối được mọi thị trấn với thị trấn \(1\), tức một cây khung nhỏ nhất theo mức phí. Nếu có nhiều cây khung nhỏ nhất, ông được chọn bất kỳ cây nào trong số đó.

Doanh thu trên một đường bằng phí của đường nhân với số người đi qua đường đó. Greedy chỉ nhận doanh thu từ \(K\) đường mới. Ông muốn đồng thời chọn mức phí cho các đường mới và chọn một cây khung nhỏ nhất sao cho tổng doanh thu từ các đường mới là lớn nhất. Hãy tính doanh thu tối đa này.

Dữ liệu vào

• Dòng đầu chứa \(N,M,K\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(a_i,b_i,c_i\), mô tả đường cũ hai chiều nối \(a_i\) với \(b_i\) có phí \(c_i\).
• \(K\) dòng tiếp theo, dòng thứ \(i\) chứa \(x_i,y_i\), mô tả một đường mới nối \(x_i\) với \(y_i\).
• Dòng cuối chứa \(N\) số \(p_1,p_2,\ldots,p_N\).

Dữ liệu ra

In tổng doanh thu lớn nhất Greedy có thể thu được.

Ràng buộc

• \(1\le N\le100\,000\).
• \(1\le M\le300\,000\).
• \(1\le K\le20\).
• \(1\le c_i,p_j\le10^6\).
• Các giá trị \(c_i\) đôi một khác nhau.
• Giữa hai thị trấn bất kỳ có nhiều nhất một con đường, tính cả đường cũ và đường mới.
• Có thể đi từ thị trấn \(1\) đến mọi thị trấn khác bằng các đường cũ.

Ví dụ

5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50

400

Giải thích

Greedy đặt phí đường mới \((1,3)\) bằng \(5\). Ông có thể chọn các đường \((3,5)\), \((1,2)\), \((2,4)\) và \((1,3)\), có tổng phí nhỏ nhất là \(14\). Có \(30+50\) người đi qua đường mới, nên doanh thu là \((30+50)\times5=400\).

Nếu đặt phí đường mới bằng \(10\), cây khung nhỏ nhất duy nhất dùng đường cũ \((2,3)\) thay cho \((1,3)\), nên đường mới không tạo doanh thu.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2013, bài Toll.