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

3 2
10 5 20
5 3 30
8 2 15
1 2 3
2 3 4

Output

547

Thành phố $1$ chở hết $10$ đơn vị hàng sang thành phố $2$ bán: $10 imes (30 - 5 - 3) = 220$. Thành phố $2$ bán tại chỗ: $5 imes (30 - 3 - 0) = 135$. Thành phố $3$ chở sang thành phố $2$: $8 imes (30 - 2 - 4) = 192$. Tổng lợi nhuận $220 + 135 + 192 = 547$.

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$