#include <iostream>
#include <fstream>
#include <string>
#include <memory>
#include <queue>

class Anus;
typedef std::shared_ptr<Anus> anus_ptr;

class Anus
{
    public:
        Anus(double p, std::string name = "") :
            name(name), p(p) {}
        std::string name;
        double p;
        //bool operator < (Anus &rhs) {return this->p < rhs.p;}
        //bool operator > (Anus &rhs) {return this->p > rhs.p;}
        anus_ptr leftChild;
        anus_ptr rightChild;
        std::string code;
};


class PAnusComparator
{
    public:
        bool operator()(anus_ptr &lhs, anus_ptr &rhs) {
            return lhs->p > rhs->p;
        }
};

class CodeAnusComparator
{
    public:
        bool operator()(anus_ptr &lhs, anus_ptr &rhs) {
            return lhs->code.size() > rhs->code.size();
        }
};

typedef std::priority_queue<anus_ptr,
        std::vector<anus_ptr>,PAnusComparator> anus_queue;

typedef std::priority_queue<anus_ptr,
        std::vector<anus_ptr>,CodeAnusComparator> code_anus_queue;

void treeSearch(anus_ptr node, code_anus_queue &yolo)
{
    if (node->name != "") //lel
        yolo.push(node);
    if (node->leftChild) {
        node->leftChild->code = node->code;
        node->leftChild->code.append("1");
        treeSearch(node->leftChild, yolo);
    }

    if (node->rightChild) {
        node->rightChild->code = node->code;
        node->rightChild->code.append("0");
        treeSearch(node->rightChild, yolo);
    }
}


int main()
{
    std::fstream swag("input.txt", std::fstream::in);

    anus_queue queue;
    std::string naem;
    double pe;

    while ((swag >> naem >> pe)) {
        queue.emplace(anus_ptr(new Anus(pe,naem)));
    }

    while (queue.size() > 1) {
        anus_ptr ptr1(queue.top());
        queue.pop();
        anus_ptr ptr2(queue.top());
        queue.pop();
        
        anus_ptr newPtr(new Anus(ptr1->p + ptr2->p));
        newPtr->leftChild = ptr1;
        newPtr->rightChild = ptr2;

        queue.emplace(anus_ptr(newPtr));
    }

    anus_ptr batya = queue.top();
    queue.pop();
    code_anus_queue resultQueue;
    treeSearch(batya, resultQueue);

    while (resultQueue.size() > 0) {
        anus_ptr kek = resultQueue.top();
        std::cout << kek->name << ": " << kek->code << std::endl;
        resultQueue.pop();
    }

    return 0;
}