미니멀리스트 보안

어느 도시의 도로망 지도가 주어진다. 도로망은 교차로와 이들을 잇는 양방향 거리로 이루어져 있다. 거리는 교차로에서만 만나며, 그 밖의 지점에서는 터널이나 고가도로로 엇갈려 지나갈 수 있다. 두 교차로를 잇는 거리는 많아야 하나뿐이다.

각 교차로 $v$에는 경찰관 $p(v)$명이 근무하는 경찰서가 있다. 교차로 $u$와 $v$를 잇는 거리는 양 끝 두 경찰서에 근무하는 경찰관 수의 합이 $b(u,v)$명 이상일 때 안전하다고 한다. 처음에는 모든 거리에 대해 $p(u) + p(v) \ge b(u,v)$가 성립한다.

위기 상황이 계속되자 시장은 최소 보안 법안(MSA)을 공포하였다. 그 내용은 다음과 같다.

• 각 경찰서에서 일정 수(0명일 수도 있다)의 경찰관을 해고한다. 교차로 $v$의 경찰서에서 해고하는 인원을 $z(v)$라 하면 $0 \le z(v) \le p(v)$이다.
• 해고가 끝난 뒤, 두 교차로 $u$와 $v$를 잇는 모든 거리에서 양 끝 경찰관 수의 합이 정확히 $b(u,v)$가 되어야 한다. 즉 $p(u) - z(u) + p(v) - z(v) = b(u,v)$이다.

이 규칙만으로는 해고 인원이 하나로 정해지지 않는다. 규칙을 지키면서 해고되는 경찰관 수의 총합, 곧 모든 교차로에 대한 $z(v)$의 합이 될 수 있는 최솟값과 최댓값을 구하여라. 법안을 시행할 수 없다면 그 사실을 알려라.

첫째 줄에 교차로의 수 $n$과 거리의 수 $m$이 공백을 두고 주어진다($1 \le n \le 500{,}000$, $0 \le m \le 3{,}000{,}000$). 교차로는 $1$번부터 $n$번까지 번호가 매겨져 있다.

둘째 줄에 각 경찰서에 현재 근무하는 경찰관 수 $p(1), p(2), \ldots, p(n)$이 공백을 두고 주어진다($0 \le p(i) \le 10^6$).

이어지는 $m$개의 줄에는 각 거리의 정보가 세 정수 $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$). 이는 각각 거리가 잇는 두 교차로와 그 양 끝에 필요한 경찰관 수의 최솟값을 뜻한다.

일부 시험 자료는 추가로 $n \le 2{,}000$, $m \le 8{,}000$을 만족한다.

법안을 시행할 수 있다면, 해고해야 하는 경찰관 수의 최솟값과 최댓값을 공백을 두고 한 줄에 출력한다.

법안을 시행할 수 없다면, NIE(폴란드어로 '아니오')라는 단어만 한 줄에 출력한다.