#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#include<set>
#pragma GCC optimize(2, 3, "Ofast", "inline")
using namespace std;

const int N=270000+10,M=10010;
//左右端点0~19999
int idx=20001,duandian=0;
int l[N],r[N]; //duandian/2+1 为单词数
string e[N];

vector<string> dancibiao;  //记录答案
unordered_map<int,int> jiedian_danci; //统计每个节点属于的单词


unordered_map<string,int> rongyu;  //每次由新的组合更改双链表之后 组合的前一个字母与前 组合的后一个字母与后就是冗余数据
unordered_map<string,set<int>> pinjiepos; //一个组合 前半段结点所在的位置

int n,m;  //n 单词  m 规定词汇表所需个数

typedef pair<int,pair<int,string>>  PIIS;

struct Danci
{
    int left,right;
    int pinlv;
}dc[M];

struct Node
{
    int cnt;
    int size;
    int front_size;
    string str;
    Node(int a,int b,int c,string s)
    {
        cnt=a;
        size=b;
        front_size=c;
        str=s;
    }
    bool operator< (const Node& t)const
    {
        if(cnt!=t.cnt)
        {
            return cnt<t.cnt;
        }
        else if(size!=t.size)
        {
            return size>t.size;
        }
        else if(front_size!=t.front_size)
        {
            return front_size>t.front_size;
        }
        else 
            return str>t.str;

    }
};

priority_queue<Node> dagendui;


//在编号为k的节点之后插入
void add(int k,string x)
{
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;
    r[k]=idx++;
}
void chutai()
{

    set<string> tongji; 

    unordered_map<string,int> cishu;
    unordered_map<string,string> dancizucheng;
    for(int c=1;c<=n;c++)
    {
        string danci;
        cin>>danci>>dc[c].pinlv;
        dc[c].left=duandian;
        dc[c].right=duandian+1;
        //初始化双链表
        l[dc[c].right]=dc[c].left;
        r[dc[c].left]=dc[c].right;
        duandian+=2;


        for(int i=0;i<danci.size();i++)
        {
            jiedian_danci[idx]=c;
            string str=string(1,danci[i]);
            int pos=idx;//当前结点的idx
            add(l[dc[c].right],str);
            tongji.insert(str);

            if(i+1<danci.size())
            {
                string pinjie;
                pinjie=string(1,danci[i])+string(1,danci[i+1]);


                pinjiepos[pinjie].insert(pos);
                if(!dancizucheng.count(pinjie))
                    dancizucheng[pinjie]=string(1,danci[i]);
                cishu[pinjie]+=dc[c].pinlv;
            }
        }
    }
    for(auto t:cishu) 
    {
        Node n(t.second,t.first.size(),dancizucheng[t.first].size(),t.first);
        dagendui.push(n);
    }
    for(auto t:tongji)
        dancibiao.push_back(t);
}
bool allone()
{
    for(int i=1;i<=n;i++)
    {
        int left=dc[i].left,right=dc[i].right;
        if(r[r[left]]!=right)
            return false; 
    }
    return true;
}

string paochu()
{
    auto ding=dagendui.top();
    dagendui.pop();
    //消除堆顶的冗余数据
    while(rongyu.count(ding.str))
    {
        ding.cnt-=rongyu[ding.str];
        rongyu.erase(ding.str);
        dagendui.push(ding);

        ding=dagendui.top();
        dagendui.pop();
    }

    return ding.str;
}

void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}
void hebing_shanchu(set<int> pos)
{
    vector<int> xulie;
    for(auto t:pos)
        xulie.push_back(t);

    for(int i=0;i<xulie.size();i++)
    {

        if(l[xulie[i]]>20000)
        {
            string str=e[l[xulie[i]]]+e[xulie[i]];
            rongyu[str]+=dc[jiedian_danci[xulie[i]]].pinlv;
            pinjiepos[str].erase(l[xulie[i]]);
        }

        int pos=r[xulie[i]];
        if(r[pos]>20000)
        {
            string str=e[pos]+e[r[pos]];
            rongyu[str]+=dc[jiedian_danci[pos]].pinlv;
            pinjiepos[str].erase(pos);
        }

        e[xulie[i]]+=e[r[xulie[i]]];
        remove(r[xulie[i]]);    
    }
}
void zeng(set<int> pos)
{
    vector<int> xulie;
    vector<int> p;
    for(auto t:pos)
        p.push_back(t);

    int i=0,j=0;
    unordered_map<string,int> tongji;
    unordered_map<string,string> dancizucheng;
    for(;i<p.size();)
    {
        //找出节点相邻的位置
        xulie.clear();
        if(l[p[i]]>20000)
            xulie.push_back(l[p[i]]);
        xulie.push_back(p[i]);
        for(j=i+1;j<p.size();)
        {
            if(r[xulie.back()]==p[j]&&j<p.size())
            {
                xulie.push_back(p[j]);
                j++;
            }
            else break;
        }
        i=j;
        if(r[xulie.back()]>20000)
            xulie.push_back(r[xulie.back()]);

        for(int i=0;i<xulie.size();i++)
        {
            if(i+1<xulie.size())
            {
                string pinjie=e[xulie[i]]+e[xulie[i+1]];
                tongji[pinjie]+=dc[jiedian_danci[xulie[i]]].pinlv;
                if(!dancizucheng.count(pinjie))
                    dancizucheng[pinjie]=e[xulie[i]];
                pinjiepos[pinjie].insert(xulie[i]);
            }
        }
    }

    for(auto t:tongji)
    {
        Node n(t.second,t.first.size(),dancizucheng[t.first].size(),t.first);
        dagendui.push(n);
    }
}
int main()
{

    cin>>n>>m;
    chutai();

    while(dancibiao.size()<m&&!allone())
    {
        string xincihui=paochu();
        dancibiao.push_back(xincihui);
        hebing_shanchu(pinjiepos[xincihui]);
        zeng(pinjiepos[xincihui]);
        pinjiepos.erase(xincihui);
    }

    for(auto t:dancibiao)
        cout<<t<<endl;


    return 0;
}