#include<fstream>
#include<deque>


#define INF 1000000000000000000LL
#define N 1000100
#define D 10000

using namespace std;

ofstream g("huffman.out");

int n,i,x,m,poz = D,a0,a1,b0,b1,l[N],v[N];

long long c[N],lg;

pair<long long,int> a[N],b[N];

pair<int,int>fi[2 * N];
pair<long long, int>fs,fd;

char buf[D];

inline int ianr(){
    unsigned int nr=0;

    while((buf[poz] < '0' || buf[poz] > '9') && buf[poz] != '-')
        if(++ poz >= D)
        fread(buf , D , 1 , stdin) , poz = 0;

    int semn = 1;

    if(buf[poz] == '-')
    ++ poz , semn = -1;

    while('0' <= buf[poz] && buf[poz] <= '9')
    {
        nr = nr * 10 + buf[poz] - '0';

        if(++ poz >= D)
            fread(buf , D , 1 , stdin) , poz = 0;
    }
    return nr * semn;
}

inline pair<long long,int> iaper(){
    pair<long long,int>x,y;

    if(a0 <= a1)
        x = a[a0];
    else
        x = make_pair(INF,0);

    if(b0 <= b1)
        y = b[b0];
    else
        y = make_pair(INF,0);

    if(x < y)
    {
        ++a0;

        return x;
    }
    else
    {
        ++b0;

        return y;
    }
}

inline void dfs(int x,int niv,long long cod){
    if(x <= n)
    {
        lg += niv * v[x];

        c[x] = cod;
        l[x] = niv;

        return;
    }

    dfs(fi[x].first, niv + 1, cod * 2);
    dfs(fi[x].second, niv + 1, cod * 2 + 1);
}

int main()
{
    freopen("huffman.in","r",stdin);

    n = ianr();

    for(int i = 1; i <= n; ++i)
    {
        v[i] = ianr();

        a[++a1] = make_pair(1LL * v[i],i);
    }

    a0 = b0 = 1;

    m = n;

    for(int i = 1; i < n; ++ i)
    {
        fs = iaper();
        fd = iaper();

        fi[++m] = make_pair(fs.second, fd.second);

        b[++b1] = make_pair(fs.first + fd.first, m);
    }

    dfs(m,0,0);

    g << lg << '\n';

    for(int i = 1; i <= n; ++i)
        g << l[i] << ' ' << c[i] <<'\n';

    return 0;
}