#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];

queue<int> Q1, Q2;
int extrage()
{
    int r;
    if(Q1.size() == 0)
    {
        r = Q2.front();
        Q2.pop();
        return r;
    }
    if(Q2.size() == 0)
    {
        r = Q1.front();
        Q1.pop();
        return r;
    }
    if(d[Q2.front()].val < d[Q1.front()].val)
    {
        r = Q2.front();
        Q2.pop();
        return r;
    }
    r = Q1.front();
    Q1.pop();
    return r;
}

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