CVP Training

Đất nước xXx có N thành phố và M con đường 2 chiều. Mỗi con đường nối 2 thành phố với nhau (không nhất thiết phân biệt). Một cặp thành phố có thể được nối với nhau bởi nhiều hơn 1 con đường. Nước yYy đang có âm mưu muốn xâm lược xXx. Cụ thể, để chiếm được thành phố i có 2 cách:

• Gửi A[i] quân lính đến phá thành phố này.
• Nếu một thành phố j có đường nối đến i mà j đã bị đánh chiếm và đang có sẵn X quân lính ở cả 2 thành phố i, j thì chỉ cần gửi W[i,j]-X quân lính đến để phá đường (i-j) và chiếm thành phố i.

Biết chi phí để gửi x quân lính đến thành phố i là B[i]*x, tính tổng chi phí tối thiểu để chiếm được toàn bộ N thành phố ?

Input

Dòng đầu tiên chứa 2 số nguyên dương N và M (1 ≤ N, M ≤ 10⁵).

Trong N dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương A[i] và B[i] (0 ≤ A[i], B[i] ≤ 10⁶).

Trong M dòng cuối cùng, mỗi dòng ghi 3 số nguyên dương U, V và W[U,V] (1 ≤ U, V ≤ N, 0 ≤ W[U,V] ≤ 10⁶).

Output

Chi phí tối thiểu tính được.

Example

Input:
3 2
10 5
20 10
10 3
1 2 22
2 3 200

Output:
140