#include <iostream>
#include <fstream>
using namespace std;
FILE *fin = fopen("huffman.in", "r");
FILE *fout = fopen("huffman.out", "w");
#define MAX 1000100
unsigned const maxb = 666013;
char buf[maxb];
unsigned ptr = maxb - 1;

int getInt()
{
    int nr = 0;
    while(!(buf[ptr] <= '9' && buf[ptr] >= '0'))
    {
        if(++ptr >= maxb)
        {
            fread(buf, maxb, 1, fin);
            ptr = 0;
        }
    }
    while((buf[ptr] <= '9' && buf[ptr] >= '0'))
    {
        nr = nr * 10 + buf[ptr] - '0';
        if(++ptr >= maxb)
        {
            fread(buf, maxb, 1, fin);
            ptr = 0;
        }
    }
    return nr;
}

struct nod{
long long val;
int st, dr;
}d[2 * MAX];

int st2, dr2, st1, dr1, Q1[MAX], Q2[MAX];
int extrage()
{
    int r;
    if(st1 > dr1)
        return Q2[st2++];
    if(st2 > dr2)
        return Q1[st1++];
    if(d[Q2[st2]].val < d[Q1[st1]].val)
        return Q2[st2++];
    return Q1[st1++];
}

long long sol, b[MAX];
int a[MAX], n;

void df(int x, int lg, long long y)
{
    if(x <= n)
    {
        sol += 1ll * lg * d[x].val;
        a[x] = lg;
        b[x] = y;
        return;
    }
    df(d[x].st, lg + 1, 2ll * y);
    df(d[x].dr, lg + 1, 2ll * y + 1);
}

int main()
{
    int i, dr;
    n = getInt();
    st1 = st2 = 1;
    for(i = 1 ; i <= n ; i++)
    {
        d[i].val = getInt();
        Q1[++dr1] = i;
    }
    dr = n;
    for(i = 1 ; i < n ; i++)
    {
        int x = extrage();
        int y = extrage();
        ++dr;
        d[dr].val = d[x].val + d[y].val;
        d[dr].st = x;
        d[dr].dr = y;
        Q2[++dr2] = dr;
    }
    int root = extrage();
    df(root, 0, 0);
    fprintf(fout, "%lld\n", sol);
    for(i = 1 ; i <= n ; i++)
    {
        fprintf(fout, "%d %lld\n", a[i], b[i]);
    }
}