Minimalist Security

You are given a map of a city's road network. The network consists of intersections and bidirectional streets connecting them. Streets meet only at intersections, but elsewhere they may cross via tunnels or overpasses. Each pair of intersections is joined by at most one street.

At every intersection $v$ there is a police station staffed by $p(v)$ officers. A street joining intersections $u$ and $v$ is safe if the two stations at its ends hold at least $b(u,v)$ officers in total. Initially $p(u) + p(v) \ge b(u,v)$ holds for every street.

Because of an ongoing crisis, the mayor has decreed the Minimalist Security Act (MSA):

• some number (possibly zero) of officers is dismissed from each station; let $z(v)$ be the number dismissed from the station at intersection $v$, so $0 \le z(v) \le p(v)$;
• after the dismissals, every street joining two intersections $u$ and $v$ must hold exactly $b(u,v)$ officers across its two ends, that is $p(u) - z(u) + p(v) - z(v) = b(u,v)$.

These rules do not fix the dismissals uniquely. Find the minimum and the maximum possible total number of dismissed officers, that is the sum of $z(v)$ over all intersections, or report that the decree cannot be carried out.

The first line contains two integers $n$ and $m$ ($1 \le n \le 500{,}000$, $0 \le m \le 3{,}000{,}000$): the number of intersections and the number of streets. Intersections are numbered from $1$ to $n$.

The second line contains $n$ nonnegative integers $p(1), p(2), \ldots, p(n)$ ($0 \le p(i) \le 10^6$): the number of officers currently at each station.

Each of the next $m$ lines contains three integers $u_i$, $v_i$, $b(u_i, v_i)$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le b(u_i, v_i) \le 10^6$): the two intersections joined by the street and the minimum total number of officers required at its ends.

A subset of the tests additionally satisfies $n \le 2{,}000$ and $m \le 8{,}000$.

If the decree can be carried out, print one line with two integers separated by a single space: the minimum and the maximum total number of officers that must be dismissed.

If the decree cannot be carried out, print a single line containing the word NIE (Polish for no).