#include<fstream>
#include<deque>


#define INF 1000000000000000000LL
#define N 1000100

using namespace std;

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

int n,i,x,m,l[N],v[N];

long long c[N],lg;

deque<pair<long long,int> >a,b;

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

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

    if(!a.empty())
        x = a.front();
    else
        x = make_pair(INF,INF);

    if(!b.empty())
        y = b.front();
    else
        y = make_pair(INF,INF);

    if(x < y)
    {
        a.pop_front();

        return x;
    }
    else
    {
        b.pop_front();

        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()
{
    f >> n;

    for(i = 1; i <= n; ++i)
    {
        f >> v[i];

        a.push_back(make_pair(1LL * v[i],i));
    }

    m = n;

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

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

        b.push_back(make_pair(fs.first + fd.first, m));
    }

    dfs(m,0,0);

    g << lg << '\n';

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

    return 0;
}