Đất nước X 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 Y đang có âm mưu muốn xâm lược X.

Cụ thể, để chiếm được thành phố ~i~ có hai 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ả hai 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 hai số nguyên dương ~N~ và ~M~ ~(1 \le N, M \le 10^5)~.
• Trong ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~A[i]~ và ~B[i]~ ~(0 \le A[i], B[i] \le 10^6).~
• Trong ~M~ dòng cuối cùng, mỗi dòng ghi ba số nguyên dương ~U, V~ và ~W[U,V]~ ~(1 \le U, V \le N, 0 \le W[U,V] \le 10^6).~

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