#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;
}