regate

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
ifstream in("regate.in");
ofstream out("regate.out");
vector <int> v[400001],down[400001];
struct mazan
{
    int a,b,c;
} muchii[400001];
bool viz[400001];
bool bad[400001];
long long ans[400001];
int r[400001],cnt,n;
int dp[400001];
int daddy[400001];
long long sz[400001];
int papa[400001];
int steve[400001],vf;
vector <int> bicon[400001];
bool cmp(mazan a,mazan b)
{
    return a.c>b.c;
}
void biconex(int nod,int papa)
{
    viz[nod]=1;
    steve[++vf]=nod;
    for(auto it:v[nod])
    {
        int y=muchii[it].a+muchii[it].b-nod;
        if(y!=papa&&viz[y])
        {
            dp[nod]++;
            dp[y]--;
        }
    }
    for(auto it:v[nod])
    {
        int y=muchii[it].a+muchii[it].b-nod;
        if(!viz[y])
        {
            biconex(y,nod);
            dp[nod]+=dp[y];
        }
    }
    if(dp[nod]==0)
    {
        daddy[nod]=++cnt;
        bicon[cnt].push_back(nod);
        while(steve[vf]!=nod)
        {
            daddy[steve[vf]]=cnt;
            bicon[cnt].push_back(steve[vf--]);
        }
        vf--;
    }
}
int fada(int nod)
{
    if(papa[nod]==nod)
        return nod;
    return papa[nod]=fada(papa[nod]);
}
int suprem;
void join(int a,int b,int c)
{
    int ra=fada(a),rb=fada(b);
    if(ra==rb)
        return;
    if(bad[ra])
    {
        papa[ra]=rb;
        down[rb].push_back(ra);
        ans[ra]-=ans[rb];
        ans[ra]+=c*sz[rb];
        suprem=rb;
        return;
    }
    if(bad[rb])
    {
        papa[rb]=ra;
        down[ra].push_back(rb);
        ans[rb]-=ans[ra];
        ans[rb]+=c*sz[ra];
        suprem=ra;
        return;
    }
    if(sz[ra]>sz[rb])
    {
        papa[rb]=ra;
        down[ra].push_back(rb);
        ans[rb]-=ans[ra];
        ans[ra]+=c*sz[rb];
        ans[rb]+=c*sz[ra]-c*sz[rb];
        sz[ra]+=sz[rb];
        suprem=ra;
    }
    else
    {
        papa[ra]=rb;
        down[rb].push_back(ra);
        ans[ra]-=ans[rb];
        ans[rb]+=c*sz[ra];
        ans[ra]+=c*sz[rb]-c*sz[ra];
        sz[rb]+=sz[ra];
        suprem=rb;
    }
}
void update(int nod)
{
    for(auto it:down[nod])
    {
        ans[it]+=ans[nod];
        update(it);
    }
}
int main()
{
    int i,m;
    in>>n>>m;
    for(i=1; i<=n; i++)
    {
        in>>r[i];
        muchii[i]= {i,n+i,r[i]};
        v[i].push_back(i);
        v[n+i].push_back(i);
    }
    for(i=1; i<=m; i++)
    {
        in>>muchii[n+i].a>>muchii[n+i].b>>muchii[n+i].c;
        v[muchii[n+i].a].push_back(n+i);
        v[muchii[n+i].b].push_back(n+i);
    }
    biconex(1,0);
    for(i=1; i<=n+m; i++)
    {
        muchii[i].a=daddy[muchii[i].a];
        muchii[i].b=daddy[muchii[i].b];
    }
    for(i=n+1; i<=2*n; i++)
        bad[daddy[i]]=1;
    sort(muchii+1,muchii+n+m+1,cmp);
    for(i=1; i<=cnt; i++)
    {
        papa[i]=i;
        sz[i]=bicon[i].size();
    }
    //for(i=1; i<=n+m; i++)
    //if(muchii[i].a!=muchii[i].b)
    //out<<muchii[i].a<<" "<<muchii[i].b<<" "<<muchii[i].c<<'\n';
    for(i=1; i<=n+m; i++)
        join(muchii[i].a,muchii[i].b,muchii[i].c);
    update(suprem);
    for(i=n+1; i<=2*n; i++)
        out<<ans[daddy[i]]-r[i-n]<<'\n';
    return 0;
}