Cây có trọng số là một đơn đồ thị vô hướng, liên thông, không có chu trình, mỗi cạnh của cây có một trọng số là số nguyên dương. Giữa hai đỉnh bất kỳ của cây, luôn tồn tại và duy nhất một đường đi đơn. Ta nói khoảng cách của hai đỉnh ~x, y~ là tổng trọng số của tất cả các cạnh nằm trên đường đi đơn giữa ~x~ và ~y~. Độ phức tạp của cây được hiểu là tổng khoảng cách của tất cả các cặp đỉnh (cặp ~(u, v)~ và ~(v, u)~ được tính một lần).

Hùng có một cây có trọng số có ~n~ đỉnh, các đỉnh của cây được đánh số từ 1 đến ~n~. Tuy nhiên anh ấy đã cắt đi ~m~ cạnh, các cạnh bị cắt có trọng số là ~w_1, w_2, \dots, w_m~. Từ cây có trọng số ban đầu, bây giờ Hùng có ~m + 1~ cây có trọng số. Anh ấy muốn khôi phục lại cây ban đầu bằng cách nối thêm ~m~ cạnh với các trọng số lần lượt là ~w_1, w_2, \dots, w_m~. Việc nối phải thoả mãn rằng khi kết thúc phải tạo thành một cây. Dù vậy vẫn có thể có nhiều cách nối khác nhau, trong khi Hùng không nhớ cây ban đầu như thế nào. Anh chỉ nhớ, cây ban đầu có độ phức tạp bé. Do đó, Hùng muốn nhờ bạn dựng lại cây sao cho độ phức tạp của cây thu được là bé nhất có thể.

Yêu cầu: Tính độ phức tạp nhỏ nhất có thể của cây thu được sau khi nối lại các cạnh.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, m~ là số đỉnh của cây và số cạnh mà Hùng đã cắt.
• Dòng tiếp theo chứa ~w_1, w_2, \dots, w_m~ là trọng số của ~m~ cạnh đã bị cắt.
• Dòng thứ ~i~ trong số ~n - m - 1~ dòng tiếp theo chứa ba số nguyên dương ~u_i, v_i, c_i~ mô tả một cạnh chưa bị cắt, cạnh này nối giữa ~u_i~ và ~v_i~ với trọng số ~c_i~.

Output

• Ghi một số nguyên duy nhất là độ phức tạp của cây thu được. Do kết quả có thể rất lớn, chỉ cần in ra phần dư khi chia cho ~1000000007~.

Sample Input 1

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

Sample Output 1

99