题目描述
译自 POI 2012 Stage 3. Day 2「Bezpieczeństwo minimalistyczne」
给定一张无向图,点有点权 p(v),边有边权 b(u,v),初始时保证对每条边有 p(u)+p(v)≥b(u,v)。
现在需要减少一部分点的点权,使得对每条边都恰有 p(u)+p(v)=b(u,v).
求整张图减少的点权和的最小值和最大值。
输入格式
第一行两个整数 n 和 m(1≤n≤500 000,0≤m≤3 000 000),表示图的点数和边数。
接下来一行 n 个非负整数 p(1),p(2),…,p(n)(0≤p(i)≤106),表示点权。
接下来 m 行每行三个整数 ui,vi,b(ui,vi)(1≤ui,vi≤n,ui=vi,0≤b(ui,vi)≤106),表示边和边权。
输出格式
如果存在符合条件的方案,输出一行两个整数,表示整张图减少的点权和的最小值和最大值。
如果不存在,输出 NIE
.
样例 1
3 2
5 10 5
1 2 5
2 3 3
12 15
3 3
1 1 1
1 2 1
1 3 1
3 2 1
NIE
数据范围与提示
对于 56% 的数据有 n≤2000,m≤8000.
对于所有数据有 1≤n≤500 000,0≤m≤3 000 000.