Đồ thị con trọng số lớn nhất

Cho một đồ thị vô hướng đơn (không có khuyên, không có cạnh bội) gồm $n$ đỉnh và $m$ cạnh.

Đỉnh thứ $i$ có trọng số $a_i$, cạnh thứ $i$ có trọng số $w_i$.

Một đồ thị con là một cặp gồm một tập đỉnh $S$ và một tập cạnh $T$, thoả mãn: mọi cạnh trong $T$ đều có cả hai đầu mút nằm trong $S$.

Trọng số của một đồ thị con bằng tổng trọng số các cạnh trong $T$ trừ đi tổng trọng số các đỉnh trong $S$.

Hãy tìm trọng số lớn nhất của một đồ thị con của đồ thị đã cho. Đồ thị con rỗng (không chọn đỉnh nào, không chọn cạnh nào) cũng hợp lệ và có trọng số $0$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số đỉnh và số cạnh của đồ thị.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: trọng số các đỉnh.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $v_i$, $u_i$, $w_i$: cạnh thứ $i$ nối hai đỉnh $v_i$ và $u_i$, có trọng số $w_i$.

Dữ liệu ra

Một số nguyên duy nhất: trọng số lớn nhất của một đồ thị con.

Ràng buộc

• $1\le n\le {10}^3$, $0\le m\le {10}^3$
• $1\le a_i\le {10}^9$
• $1\le v_i,u_i\le n$, $v_i\ne u_i$
• $1\le w_i\le {10}^9$
• Đồ thị không có khuyên và không có cạnh bội.

Ví dụ