#include <iostream>
#include <queue>
using namespace std;

struct node {
    char value;
    int freq;
    
    node * left,  * right;
    
    node(char _value, int _freq) {
        value = _value;
        freq = _freq;
        left = NULL;
        right = NULL;
    }
};
struct cmp {
    bool operator() (node * n1, node * n2) {
        return (n1->freq > n2->freq);
    }
};
void dfs(node * root, string s) {
    if(!root) {
        return;
    }
    if(root->value != '#') {
        cout << root-> value << ": " << s << endl;
    }
    dfs(root->left, s + "0");
    dfs(root->right, s + "1");
}
void huffman_coding(vector<char> chars, vector<int> freq) {
    priority_queue<node *, vector<node *>, cmp> pq;
    for(int i = 0; i < (int) chars.size(); i++) {
        pq.push(new node(chars[i], freq[i]));
    }
    
    while(pq.size() > 1) {
        node * left = pq.top();
        pq.pop();
        
        node * right = pq.top();
        pq.pop();
        
        node * root = new node('#', left->freq + right -> freq);
        root->left = left;
        root->right = right;
        pq.push(root);
    }
    
    dfs(pq.top(), "");
}
int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<char> chars(n);
    vector<int> freq(n);
    for(int i = 0; i < n; i++) {
        cin >> chars[i] >> freq[i];
    }
    
    huffman_coding(chars, freq);
    return 0;
}
/*
 6
 a 5
 b 9
 c 12
 d 13
 e 16
 f 45
 
 **/