#include <iostream>
#include <fstream>
#include <queue>
//#include <conio.h>
using namespace std;
ifstream fin("huffman.in");
ofstream fout("huffman.out");
#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)
        {
            fin.read(buf, maxb);
            ptr = 0;
        }
    }
    while((buf[ptr] <= '9' && buf[ptr] >= '0'))
    {
        nr = nr * 10 + buf[ptr] - '0';
        if(++ptr >= maxb)
        {
            fin.read(buf, maxb);
            ptr = 0;
        }
    }
    return nr;
}

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

int st2, dr2, st1, dr1, Q1[MAX], Q2[MAX];
int extrage()
{
   //cout << st1 << " " << dr1 << " " << st2 << " " << dr2 << "\n";
    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];

void df(int x, int lg, long long y)
{
 //   cout << x->val << " " << lg << ' ' << y << " " << x->st->val << " " << x->dr->val <<  "\n";
   // getch();
    if(d[x].ind)
    {
        sol += 1ll * lg * d[x].val;
        a[d[x].ind] = lg;
        b[d[x].ind] = y;
        return;
    }
    df(d[x].st, lg + 1, 2ll * y);
    df(d[x].dr, lg + 1, 2ll * y + 1);
}

int main()
{
    int n, i, dr;
    n = getInt();
    st1 = st2 = 1;
    for(i = 1 ; i <= n ; i++)
    {
        d[i].val = getInt();
        d[i].ind = i;
        d[i].st = d[i].dr = 0;
        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;
       // cout << z->val << " " << z->st->val << " " << z->dr->val << "\n";
        d[dr].ind = 0;
        Q2[++dr2] = dr;
    }
    int root = extrage();
    df(root, 0, 0);
    fout << sol << "\n";
    for(i = 1 ; i <= n ; i++)
    {
        fout << a[i] << " " << b[i] << "\n";
    }
}