#include <bits/stdc++.h> 
using namespace std;
int n;
int cost[1010];
int a,b,c;
vector<int> s[1010];
vector<int> zhi[1010];
int ru[1010];
queue<int> yao;
int f[1010];
int fang[1010];
void topo()
{
    queue<int> q;
    for(int i=0;i<n;i++)
    {
        if(ru[i]==0)
        {
            q.push(i);
            yao.push(i);
        }
    }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=0;i<s[t].size();i++)
        {
            ru[s[t][i]]--;
            if(ru[s[t][i]]==0)
            {
                q.push(s[t][i]);
                yao.push(s[t][i]);
            }
        }
    }
}
int ans;
bool vis[1010];
void dfs(int x)
{
    if(vis[x]) return ;
    vis[x]=1;
    ans+=fang[x];
    for(int i=0;i<s[x].size();i++)
    {
        dfs(zhi[x][i]);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",cost+i);
        fang[i]=1;
        f[i]=0x3fff;
    }
    while(cin>>a>>b>>c)
    {
        s[a].push_back(c);
        s[b].push_back(c);
        zhi[c].push_back(a);
        zhi[c].push_back(b);
        ru[c]+=2;
    }
    topo();
    int t;
    while(!yao.empty())
    {
        t=yao.front();
        yao.pop();
        if(t==2)
        {
            
        }
        if(zhi[t].size()==2)
        {
            int zuo,you;
            zuo=zhi[t][0];
            you=zhi[t][1];
            cout<<cost[t]<<" "<<f[zuo]+f[you]<<endl;
            f[t]=min(cost[t],f[zuo]+f[you]);
            if(cost[t]==f[zuo]+f[you]) fang[t]++;
        }
        else f[t]=cost[t];
    }
    for(int i=0;i<n;i++)
    {
        cout<<fang[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<f[i]<<" ";
    }
    cout<<endl;
    dfs(0);
    cout<<f[0]<<" "<<ans;
    return 0;
}