#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct edge{
int dest, wt;
char tag;
};
const ll a = 137, mod = 1000000007;
vector<edge> adj[1010];
string str;
ll pa[10100], dist[1010];
map<pair<ll, int>, ll> m1;
typedef pair<ll, pair<int, pair<ll, int> > > ds;
int main()
{
//freopen("i.txt", "r", stdin);
int n, m, i, j, u, v, cur, z;
char c;
ll hash, x, y, cdist, chash, ndist, nhash, clen;
pa[0] = 1;
for(i=1; i<=10000; i++)
pa[i] = (pa[i-1]*a)%mod;
scanf("%d%d", &n, &m);
for(i=0; i<m; i++){
scanf("%d%d%d %c", &u, &v, &z, &c);
adj[u].push_back((edge){v, z, c});
adj[v].push_back((edge){u, z, c});
}
cin >> str;
for(i=0; i<str.size(); i++){
hash = 0;
for(j=i; j<str.size(); j++){
x = (pa[j-i]*1ll*(str[j]-'a'))%mod;
hash = (hash+x)%mod;
m1[make_pair(hash, j-i+1)]++;
}
}
//cout << m1[make_pair(0, 1)] << "\n";
for(i=1; i<=n; i++)
dist[i] = INT_MAX;
priority_queue< ds, vector< ds >, greater< ds > > pq;
pq.push(make_pair(0, make_pair(1, make_pair(0, 0))));
dist[0] = 0;
while(!pq.empty()){
cdist = pq.top().first;
cur = pq.top().second.first;
chash = pq.top().second.second.first;
clen = pq.top().second.second.second;
pq.pop();
if(cdist>dist[cur])
continue;
for(i=0; i<adj[cur].size(); i++){
x = (pa[clen]*1ll*(adj[cur][i].tag - 'a'))%mod;
nhash = (chash+x)%mod;
if(m1.find(make_pair(nhash, clen+1))==m1.end())
continue;
ndist = cdist + (m1[make_pair(nhash, clen+1)]*(adj[cur][i].wt));
if(ndist < dist[adj[cur][i].dest]){
dist[adj[cur][i].dest] = ndist;
pq.push(make_pair(ndist, make_pair(adj[cur][i].dest, make_pair(nhash, clen+1))));
}
}
}
printf("%lld\n", dist[n]);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBsbCBsb25nIGxvbmcKCnN0cnVjdCBlZGdlewoJaW50IGRlc3QsIHd0OwoJY2hhciB0YWc7Cn07Cgpjb25zdCBsbCBhID0gMTM3LCBtb2QgPSAxMDAwMDAwMDA3OwoKdmVjdG9yPGVkZ2U+IGFkalsxMDEwXTsKc3RyaW5nIHN0cjsKbGwgcGFbMTAxMDBdLCBkaXN0WzEwMTBdOwptYXA8cGFpcjxsbCwgaW50PiwgbGw+IG0xOwoKdHlwZWRlZiBwYWlyPGxsLCBwYWlyPGludCwgcGFpcjxsbCwgaW50PiA+ID4gZHM7CgppbnQgbWFpbigpCnsKCS8vZnJlb3BlbigiaS50eHQiLCAiciIsIHN0ZGluKTsKCWludCBuLCBtLCBpLCBqLCB1LCB2LCBjdXIsIHo7CgljaGFyIGM7CglsbCBoYXNoLCB4LCB5LCBjZGlzdCwgY2hhc2gsIG5kaXN0LCBuaGFzaCwgY2xlbjsKCXBhWzBdID0gMTsKCWZvcihpPTE7IGk8PTEwMDAwOyBpKyspCgkJcGFbaV0gPSAocGFbaS0xXSphKSVtb2Q7CglzY2FuZigiJWQlZCIsICZuLCAmbSk7Cglmb3IoaT0wOyBpPG07IGkrKyl7CgkJc2NhbmYoIiVkJWQlZCAlYyIsICZ1LCAmdiwgJnosICZjKTsKCQlhZGpbdV0ucHVzaF9iYWNrKChlZGdlKXt2LCB6LCBjfSk7CgkJYWRqW3ZdLnB1c2hfYmFjaygoZWRnZSl7dSwgeiwgY30pOwoJfQoJY2luID4+IHN0cjsKCWZvcihpPTA7IGk8c3RyLnNpemUoKTsgaSsrKXsKCQloYXNoID0gMDsKCQlmb3Ioaj1pOyBqPHN0ci5zaXplKCk7IGorKyl7CgkJCXggPSAocGFbai1pXSoxbGwqKHN0cltqXS0nYScpKSVtb2Q7CgkJCWhhc2ggPSAoaGFzaCt4KSVtb2Q7CgkJCW0xW21ha2VfcGFpcihoYXNoLCBqLWkrMSldKys7CgkJfQoJfQoJLy9jb3V0IDw8IG0xW21ha2VfcGFpcigwLCAxKV0gPDwgIlxuIjsKCWZvcihpPTE7IGk8PW47IGkrKykKCQlkaXN0W2ldID0gSU5UX01BWDsKCXByaW9yaXR5X3F1ZXVlPCBkcywgdmVjdG9yPCBkcyA+LCBncmVhdGVyPCBkcyA+ID4gcHE7CglwcS5wdXNoKG1ha2VfcGFpcigwLCBtYWtlX3BhaXIoMSwgbWFrZV9wYWlyKDAsIDApKSkpOwoJZGlzdFswXSA9IDA7Cgl3aGlsZSghcHEuZW1wdHkoKSl7CgkJY2Rpc3QgPSBwcS50b3AoKS5maXJzdDsKCQljdXIgPSBwcS50b3AoKS5zZWNvbmQuZmlyc3Q7CgkJY2hhc2ggPSBwcS50b3AoKS5zZWNvbmQuc2Vjb25kLmZpcnN0OwoJCWNsZW4gPSBwcS50b3AoKS5zZWNvbmQuc2Vjb25kLnNlY29uZDsKCQlwcS5wb3AoKTsKCQlpZihjZGlzdD5kaXN0W2N1cl0pCgkJCWNvbnRpbnVlOwoJCWZvcihpPTA7IGk8YWRqW2N1cl0uc2l6ZSgpOyBpKyspewoJCQl4ID0gKHBhW2NsZW5dKjFsbCooYWRqW2N1cl1baV0udGFnIC0gJ2EnKSklbW9kOwoJCQluaGFzaCA9IChjaGFzaCt4KSVtb2Q7CgkJCWlmKG0xLmZpbmQobWFrZV9wYWlyKG5oYXNoLCBjbGVuKzEpKT09bTEuZW5kKCkpCgkJCQljb250aW51ZTsKCQkJbmRpc3QgPSBjZGlzdCArIChtMVttYWtlX3BhaXIobmhhc2gsIGNsZW4rMSldKihhZGpbY3VyXVtpXS53dCkpOwoJCQlpZihuZGlzdCA8IGRpc3RbYWRqW2N1cl1baV0uZGVzdF0pewoJCQkJZGlzdFthZGpbY3VyXVtpXS5kZXN0XSA9IG5kaXN0OwoJCQkJcHEucHVzaChtYWtlX3BhaXIobmRpc3QsIG1ha2VfcGFpcihhZGpbY3VyXVtpXS5kZXN0LCBtYWtlX3BhaXIobmhhc2gsIGNsZW4rMSkpKSk7CgkJCX0KCQl9Cgl9CglwcmludGYoIiVsbGRcbiIsIGRpc3Rbbl0pOwoJcmV0dXJuIDA7Cn0=