The new school term is about to begin!

In Bitland College, there are $N$ students divided into two classes: Class $0$ and class $1$. Initially, student $i$ is allocated to Class $a_i$ for each integer $1 \le i \le N$. At least two students are being initially allocated to Class $0$.

There are $M$ pairs of friends: for each $1 \le j \le M$, we know that student $u_j$ and student $v_j$ are a pair of friends with bonding $w_j$.

The harmony of a class $1$ is defined as the sum of bonding of friendships shared among the students of Class $1$.

You are the class teacher of class $1$, and you wish to teach a harmonious class.

You now have the ability to switch at most 2 students who are initially from Class $0$ to Class $1$. What is the maximum possible harmony of Class $1$ that you can achieve?

Input

The first line contains two positive integers $N$ and $M$, denoting the number of students, and the total number of pairs of friends respectively.

The second line contains $N$ non-negative integers, the $i$-th of which being $a_i$, denoting the class that the $i$-th student is being initially allocated to.

The next $M$ lines contain three positive integers each: $u_i, v_i$ and $w_i$, describing the pairs of friends.

Output

Output one integer: the maximum possible harmony of Class $1$.

Constraints

For all test cases, $2 \le N \le 2 \times 10^5$, $1 \le M \le 3 \times 10^5$, $0 \le a_i \le 1$ for all $1 \le i \le N$, $1 \le u_j \neq v_j \le N$ and $1 \le w_j \le 10^9$ for all $1 \le j \le M$, and $ (u_x, v_x) \neq (u_y, v_y)$ for all $1 \le x < y \le M$. Additionally, there are at least two students allocated to Class $0$.

Subtask 1 (9 points): $N, M \le 200$.

Subtask 2 (13 points): $a_i = 0$ for all $1 \le i \le N$.

Subtask 3 (23 points): $N \le 2000$.

Subtask 4 (25 points): For each $1 \le j \le M$, at least one of $a_{u_j} = 1$ or $a_{v_j} = 1$ hold.

Subtask 5 (30 points): No additional constraints.