/*
 * Implementacija algoritma za Huffman-ovo kodiranje.
 */

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

struct Cvor {
    Cvor(char c, int f):karakter(c),frekvencija(f){};
    char karakter;
    int frekvencija;
    Cvor *levo = nullptr;
    Cvor *desno = nullptr;
};

struct poredi {
    bool operator()(Cvor *c1, Cvor *c2)
    {
        return c1->frekvencija > c2->frekvencija;
    }
};

Cvor* huffman(vector<Cvor*> &karakteri)
{
    if(karakteri.size() == 0)
        return nullptr;
    
    priority_queue<Cvor*, vector<Cvor*>, poredi> hip;
    
    for(int i = 0; i < karakteri.size(); i++)
    {
        hip.push(karakteri[i]);
    }
    
    while(hip.size() > 1)
    {
        Cvor *levi = hip.top();
        hip.pop();
        
        Cvor *desni = hip.top();
        hip.pop();
        
        Cvor *novi = new Cvor('#', desni->frekvencija + levi->frekvencija);
        
        novi->levo = levi;
        novi->desno = desni;
        
        hip.push(novi);
    }
    
    Cvor *koren = hip.top();
    hip.pop();
    
    return koren;
}

void ispis(Cvor *koren, string niska)
{
    if(koren != nullptr)
    {
        if(koren->karakter == '#')
        {
            ispis(koren->levo, niska + "0");
            ispis(koren->desno, niska + "1");
        }
        else
        {
            cout << koren->karakter << ": " << niska << endl;
        }
    }
}

int main()
{
    vector<Cvor*> karakteri;

    int n;
    char c;
    int f;
    
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        cin >> c >> f;
         cin.get();
        karakteri.push_back(new Cvor(c,f));
    }
    
    Cvor* stablo = huffman(karakteri);

    ispis(stablo, "");
    
    return 0;
}