题目链接：戳我
首先注意这张图有可能不连通！！
然后我们考虑对于每一个联通块，首先任意确定一个点，给它设最终值为x，然后进行搜索。（因为对于一个联通块而言，我们知道一个点的最终值，那么整个联通块上面点的值就都知道了）
我们发现这些值只有-x+b或者x+b两种情况。
当一个点被访问到了第二次，如果两次x的系数一样且b不一样，就可以直接输出NIE。如果系数不一样，那么也就可以确认x的大小了（之后记得还要检验一下子）。
如果没有点被访问两次或者以上，那么就是一些不等式的限制条件，我们直接解不等式就行啦。而总数的极值一定也在x的极值上QAQ
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<ctime>
#define MAXN 500010
#define MAXM 3000010
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}
return x*f;
}
int n,m,t,cnt,tot;
int head[MAXN],p[MAXN],done[MAXN],col[MAXN],vec[MAXN];
long long minn_ans,maxx_ans;
struct Node{int k,b;}node[MAXN];
struct Edge{int nxt,to,dis;}edge[MAXM<<1];
inline void add(int from,int to,int dis)
{
edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis;
head[from]=t;
}
inline void calc(int x,int cur_ans)
{
if(cur_ans)
{
for(int i=1;i<=tot;i++)
{
int now=vec[i];
int sum=node[now].k*cur_ans+node[now].b;
if(sum<0||sum>p[now])
{
printf("NIE\n");
exit(0);
}
else
{
minn_ans+=p[now]-sum;
maxx_ans+=p[now]-sum;
}
}
}
else
{
int l=0,r=0x3f3f3f3f;
for(int i=1;i<=tot;i++)
{
int now=vec[i];
if(node[now].k==-1)
{
l=max(l,node[now].b-p[now]);
r=min(r,node[now].b);
}
else
{
l=max(l,-node[now].b);
r=min(r,p[now]-node[now].b);
}
if(l>r)
{
printf("NIE\n");
exit(0);
}
}
long long cur_ans1=0,cur_ans2=0;
for(int i=1;i<=tot;i++)
{
int now=vec[i];
cur_ans1+=p[now]-node[now].k*l-node[now].b;
cur_ans2+=p[now]-node[now].k*r-node[now].b;
}
minn_ans+=min(cur_ans1,cur_ans2);
maxx_ans+=max(cur_ans1,cur_ans2);
}
return;
}
inline void paint(int x,int color)
{
tot=0;
int cur_ans=0;
queue<int>q;
q.push(x);
node[x]=(Node){1,0};
while(!q.empty())
{
if((double)clock()/CLOCKS_PER_SEC>1.8)
{
printf("NIE\n");
exit(0);
}
int u=q.front();q.pop();
if(!col[u]) vec[++tot]=u;
col[u]=color;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
int v_k=(node[u].k==1)?-1:1;
int v_b=edge[i].dis-node[u].b;
if(!col[v])
{
node[v]=(Node){v_k,v_b};
q.push(v);
continue;
}
if(col[v]==color)
{
if(node[v].k==v_k&&node[v].b!=v_b)
{
printf("NIE\n");
exit(0);
}
if(node[v].k!=v_k)
{
int cur=(node[v].b-v_b)/(v_k-node[v].k);
if(cur*(v_k-node[v].k)!=(node[v].b-v_b))
{
printf("NIE\n");
exit(0);
}
if(!cur_ans) cur_ans=cur;
else if(cur_ans!=cur)
{
printf("NIE\n");
exit(0);
}
}
}
}
}
calc(x,cur_ans);
return;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
n=read(),m=read();
for(int i=1;i<=n;i++) p[i]=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),w=read();
add(x,y,w),add(y,x,w);
}
for(int i=1;i<=n;i++)
{
if(!col[i])
cnt++,paint(i,cnt);
}
printf("%lld %lld\n",minn_ans,maxx_ans);
return 0;
}