Cho một đồ thị vô hướng gồm $n$ đỉnh (thành phố) và $m$ cạnh (đường hai chiều).

• Mỗi thành phố $i$ có: sản lượng hàng hóa $a_i$ , chi phí sản xuất $p_i$ , đơn giá bán $s_i$

• Mỗi cạnh $u-v$ có trọng số $w$ , biểu thị chi phí đường đi khi vận chuyển mỗi đơn vị hàng hóa

• Hàng hóa có thể bán ngay tại nơi sản xuất, hoặc vận chuyển đến bất kỳ thành phố nào khác để bán

• Lợi nhuận của mỗi đơn vị hàng = đơn giá bán tại thành phố bán - chi phí sản xuất - tổng độ dài đường vận chuyển

• Mục tiêu: tính tổng lợi nhuận lớn nhất trên toàn đồ thị (hàng không có lợi nhuận thì không bán)

Dữ liệu vào

Dòng đầu tiên: hai số nguyên dương $n, m$ (số đỉnh, số cạnh)

$n$ dòng tiếp theo: mỗi dòng gồm ba số nguyên dương $a_i, p_i, s_i$ (sản lượng, chi phí, giá bán)

$m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên dương $u, v, w$ (cạnh vô hướng, độ dài đường đi)

Dữ liệu ra

In ra một số nguyên dương, biểu thị tổng lợi nhuận lớn nhất

Ví dụ

Input

Output

Ghi chú

Giới hạn dữ liệu

• $1 \le n \le 500$

• $1 \le m \le \frac{n(n-1)}{2}$

• $1 \le a_i, p_i, s_i \le 10000$