// There is nothing in a caterpillar that tells you its going to be a butterfly --------------------- !
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define f first
#define mp make_pair
#define mod 1000000007
#define s second
#define pb push_back
vector<pi>g[100011];
ll d[100011];
ll dp[100011]={0};
vector<int>P[100011];
ll inc[100011];
ll K;
ll calc(ll a,ll b){
if(a<b) swap(a,b);
double r=(double)K/ (double)a;
if(b>=r) return K+1;
return a*b;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N,M;
int u,v;
char c;
cin >> N >> M >> K;
rep(i,M){
cin >> u >> v >> c;
g[u].pb({v,c-'a'});
g[v].pb({u,c-'a'});
}
rep(i,N+1) d[i]=1e18;
queue<int>q;
q.push(N);
int t;
d[N]=0;
while(q.size()){
t=q.front();
q.pop();
for(auto x:g[t]){
if(d[x.f]>d[t]+1){
q.push(x.f);
d[x.f]=d[t]+1;
}
}
}
assert(d[1]!=1e18);
for(int i=1;i<=N;i++){
if(d[i]<=N){
P[d[i]].pb(i);
}
}
vector<pi>state;
state.pb({1,1});
int cur=0;
string s="";
dp[N]=1;
for(int i=1;i<=d[1];i++){
for(auto x:P[i]){
for(auto y:g[x]){
if(d[y.f]==i-1){
dp[x]+=dp[y.f];
if(dp[x]>K) dp[x]=K+1;
}
}
}
if(P[i].size()==0){
cout<<-1;
return 0;
}
}
if(dp[1]<K){
cout<<-1;
return 0;
}
while(cur!=d[1]){
ll sum=0;
set<pi>ns;
rep(c,26){
ll tot=0;
for(auto x:state){
for(auto u:g[x.f]){
if(d[u.f]==d[x.f]-1 and u.s==c){
tot+=calc(dp[u.f],x.s);
if(tot>K) tot=K+1;
}
}
}
if(tot>=K){
s+=char(c+'a');
for(auto x:state){
for(auto u:g[x.f]){
if(d[u.f]==d[x.f]-1 and u.s==c){
ns.erase({u.f,inc[u.f]});
inc[u.f]+=x.s;
if(inc[u.f]>=K) inc[u.f]=K+1;
ns.insert({u.f,inc[u.f]});
}
}
}
state.clear();
state=vector<pi>(ns.begin(),ns.end());
break;
}
K-=tot;
}
cur++;
}
cout<<s;
return 0;
}
Ly8gVGhlcmUgaXMgbm90aGluZyBpbiBhIGNhdGVycGlsbGFyIHRoYXQgdGVsbHMgeW91IGl0cyBnb2luZyB0byBiZSBhIGJ1dHRlcmZseSAtLS0tLS0tLS0tLS0tLS0tLS0tLS0gIQojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIHJlcChpLG4pIGZvcihpbnQgaT0wO2k8bjtpKyspCiNkZWZpbmUgbGwgIGxvbmcgbG9uZyBpbnQKI2RlZmluZSBwaSBwYWlyPGxsLGxsPgojZGVmaW5lIHBpaSBwYWlyPGxsLHBpPgojZGVmaW5lIGYgZmlyc3QKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwojZGVmaW5lIHMgc2Vjb25kCiNkZWZpbmUgcGIgcHVzaF9iYWNrCgp2ZWN0b3I8cGk+Z1sxMDAwMTFdOwpsbCBkWzEwMDAxMV07CmxsIGRwWzEwMDAxMV09ezB9Owp2ZWN0b3I8aW50PlBbMTAwMDExXTsKbGwgaW5jWzEwMDAxMV07CmxsIEs7CmxsIGNhbGMobGwgYSxsbCBiKXsKICAgIGlmKGE8Yikgc3dhcChhLGIpOwogICAgZG91YmxlIHI9KGRvdWJsZSlLLyAoZG91YmxlKWE7CiAgICBpZihiPj1yKSByZXR1cm4gSysxOwogICAgcmV0dXJuIGEqYjsKfQppbnQgbWFpbigpewoKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgaW50IE4sTTsKICAgIGludCB1LHY7CiAgICBjaGFyIGM7CiAgICBjaW4gPj4gTiA+PiBNID4+IEs7CiAgICByZXAoaSxNKXsKICAgICAgICBjaW4gPj4gdSA+PiB2ID4+IGM7CiAgICAgICAgZ1t1XS5wYih7dixjLSdhJ30pOwogICAgICAgIGdbdl0ucGIoe3UsYy0nYSd9KTsKICAgIH0KICAgIHJlcChpLE4rMSkgZFtpXT0xZTE4OwogICAgcXVldWU8aW50PnE7CiAgICBxLnB1c2goTik7CiAgICBpbnQgdDsKICAgIGRbTl09MDsKICAgIHdoaWxlKHEuc2l6ZSgpKXsKICAgICAgICB0PXEuZnJvbnQoKTsKICAgICAgICBxLnBvcCgpOwogICAgICAgIGZvcihhdXRvIHg6Z1t0XSl7CiAgICAgICAgICAgIGlmKGRbeC5mXT5kW3RdKzEpewogICAgICAgICAgICAgICAgcS5wdXNoKHguZik7CiAgICAgICAgICAgICAgICBkW3guZl09ZFt0XSsxOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgYXNzZXJ0KGRbMV0hPTFlMTgpOwogICAgZm9yKGludCBpPTE7aTw9TjtpKyspewogICAgICAgIGlmKGRbaV08PU4pewogICAgICAgICAgICBQW2RbaV1dLnBiKGkpOwogICAgICAgIH0KICAgIH0KICAgIHZlY3RvcjxwaT5zdGF0ZTsKICAgIHN0YXRlLnBiKHsxLDF9KTsKICAgIGludCBjdXI9MDsKICAgIHN0cmluZyBzPSIiOwogICAgZHBbTl09MTsKCiAgICBmb3IoaW50IGk9MTtpPD1kWzFdO2krKyl7CiAgICAgICAgZm9yKGF1dG8geDpQW2ldKXsKICAgICAgICAgICAgZm9yKGF1dG8geTpnW3hdKXsKICAgICAgICAgICAgICAgIGlmKGRbeS5mXT09aS0xKXsKICAgICAgICAgICAgICAgICAgICBkcFt4XSs9ZHBbeS5mXTsKICAgICAgICAgICAgICAgICAgICBpZihkcFt4XT5LKSBkcFt4XT1LKzE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYoUFtpXS5zaXplKCk9PTApewogICAgICAgICAgICBjb3V0PDwtMTsKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQogICAgfQogICAgCiAgICBpZihkcFsxXTxLKXsKICAgICAgICBjb3V0PDwtMTsKICAgICAgICByZXR1cm4gMDsKICAgIH0KCiAgICB3aGlsZShjdXIhPWRbMV0pewogICAgICAgIGxsIHN1bT0wOwogICAgICAgIHNldDxwaT5uczsKICAgICAgICByZXAoYywyNil7CiAgICAgICAgICAgIGxsIHRvdD0wOwogICAgICAgICAgICBmb3IoYXV0byB4OnN0YXRlKXsKICAgICAgICAgICAgICAgIGZvcihhdXRvIHU6Z1t4LmZdKXsKICAgICAgICAgICAgICAgICAgICBpZihkW3UuZl09PWRbeC5mXS0xIGFuZCB1LnM9PWMpewogICAgICAgICAgICAgICAgICAgICAgICB0b3QrPWNhbGMoZHBbdS5mXSx4LnMpOwogICAgICAgICAgICAgICAgICAgICAgICBpZih0b3Q+SykgdG90PUsrMTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGlmKHRvdD49Syl7CiAgICAgICAgICAgICAgICBzKz1jaGFyKGMrJ2EnKTsKICAgICAgICAgICAgICAgIGZvcihhdXRvIHg6c3RhdGUpewogICAgICAgICAgICAgICAgICAgIGZvcihhdXRvIHU6Z1t4LmZdKXsKICAgICAgICAgICAgICAgICAgICAgICAgaWYoZFt1LmZdPT1kW3guZl0tMSBhbmQgdS5zPT1jKXsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG5zLmVyYXNlKHt1LmYsaW5jW3UuZl19KTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluY1t1LmZdKz14LnM7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZihpbmNbdS5mXT49SykgaW5jW3UuZl09SysxOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgbnMuaW5zZXJ0KHt1LmYsaW5jW3UuZl19KTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIHN0YXRlLmNsZWFyKCk7CiAgICAgICAgICAgICAgICBzdGF0ZT12ZWN0b3I8cGk+KG5zLmJlZ2luKCksbnMuZW5kKCkpOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgSy09dG90OwogICAgICAgIH0KICAgICAgICBjdXIrKzsKICAgIH0KICAgIGNvdXQ8PHM7CiAgICByZXR1cm4gMDsKfQo=