#include <fstream>
#include <deque>

using namespace std;

#define NMAX 4000007

deque < pair < long long , int > > q[2];
long long sol[NMAX],fr[NMAX],l[NMAX],r[NMAX],len[NMAX];
int x,y,i,N,cnt;
long long to;
pair < long long , int > nod;

inline int get()
{
    pair < long long , int > nod;

    if (q[0].empty())
    {
        nod = q[1][0];
        q[1].pop_front();

        return nod.second;
    }

    if (q[1].empty())
    {
        nod = q[0][0];
        q[0].pop_front();

        return nod.second;
    }

    if (q[1][0].first>q[0][0].first)
    {
        nod = q[0][0];
        q[0].pop_front();

        return nod.second;
    }

    nod = q[1][0];
    q[1].pop_front();

    return nod.second;
}

void df(int nod,int de,long long sum)
{
    if (l[nod])
    {
        df(l[nod],de+1,2*sum);
        df(r[nod],de+1,2*sum+1);
    }
    else
    {
        len[nod] = de;
        sol[nod] = sum;
    }
}

int main()
{
ifstream f("huffman.in");
ofstream g("huffman.out");

f>>N;

for (i=1;i<=N;++i)
{
    f>>fr[i];
    q[0].push_back(make_pair(fr[i],i));
    ++cnt;
}

for (i=1;i<=N-1;++i)
{
    x = get();
    y = get();

    ++cnt;
    l[cnt] = x;
    r[cnt] = y;

    fr[cnt] = fr[x] + fr[y];

    q[1].push_back(make_pair(fr[cnt],cnt));
}

df(cnt,0,0);

for (i=1;i<=N;++i)
to += fr[i]*len[i];

for (i=1,g<<to<<'\n';i<=N;++i)
g<<len[i]<<" "<<sol[i]<<'\n';

return 0;
}