#include <fstream>
#include <limits.h>
using namespace std;
ifstream f("huffman.in");
ofstream g("huffman.out");

typedef struct nodes
{
    int value;
    nodes *l,*r;
}nodes;


void afis(nodes* root,int cod, int lv)
{
    if(root!=NULL)
    {
        if(root->l==NULL && root->r==NULL)
            g<<root->value<<' '<<lv<<' '<<cod<<'\n';
        cod=cod<<1;
        lv++;
        afis(root->l,cod,lv);
        afis(root->r,cod+1,lv);
    }
}
void huffman(int n, nodes** frecv, nodes** costs)
{
    int i=0,j=0,t=0,sum=0;
    nodes *nr1,*nr2;
    frecv[n]=(nodes*)malloc(sizeof(nodes));
    frecv[n]->value=INT_MAX;

    while(i<n || j<t-1)
    {
        if(t!=0 && costs[j]->value<frecv[i]->value)
            nr1=costs[j++];
        else
            nr1=frecv[i++];
        if(t!=0 && costs[j]->value<frecv[i]->value)
            nr2=costs[j++];
        else
            nr2=frecv[i++];

        costs[t]=(nodes*)malloc(sizeof(nodes));
        costs[t]->value=nr1->value+nr2->value;
        sum+=costs[t]->value;
        costs[t]->l=nr1;
        costs[t++]->r=nr2;
    }
    g<<sum<<'\n';
    afis(costs[t-1],0,0);
}

int main()
{
    int n,i,x;
    nodes** frecv=(nodes**)malloc(sizeof(nodes*)*1000002);
    nodes** costs=(nodes**)malloc(sizeof(nodes*)*1000002);
    f>>n;
    for(i=0;i<n;i++)
    {
        frecv[i]=(nodes*)malloc(sizeof(nodes));
        f>>frecv[i]->value;
        frecv[i]->r=NULL;
        frecv[i]->l=NULL;
    }

    huffman(n,frecv,costs);

    return 0;
}