#include "bits/stdc++.h"
//#include "atcoder/all"
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
long long dp[1000][1000];
vector<int>to[1000][26];
bool memo[1000][1000];
typedef pair<long long, pair<int, int>> P;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, M;
	cin >> N >> M;
	rep(i, M) {
		int a, b; char c;
		cin >> a >> b >> c;
		a--; b--;
		to[a][c - 'a'].push_back(b);
		to[b][c - 'a'].push_back(a);
		memo[a][b] = true;
		memo[b][a] = true;
	}
	rep(i, N) {
		rep(j, N) {
			dp[i][j] = LINF;
		}
	}
	dp[0][N - 1] = 0;
	priority_queue<P, vector<P>, greater<P> > q;//小さいもの順
	q.push({ 0,{0,N - 1} });
	long long ans = LINF;
	while (!q.empty()) {
		auto tmp = q.top();
		q.pop();
		long long cost = tmp.first;
		long long x1 = tmp.second.first;
		long long x2 = tmp.second.second;
		//cout << cost << " " << x1 << " " << x2 << endl;
		if (cost > dp[x1][x2]) {
			continue;
		}
		if (x1 == x2) {
			ans = min(ans, cost);
			continue;
		}
		if (memo[x1][x2]) {
			ans = min(ans, cost + 1);
			continue;
		}
		rep(i, 26) {
			if ((to[x1][i].size()) && (to[x2][i].size())) {
				//cout << to[x1][i].size() << " " << to[x2][i].size() << endl;
				rep(j, to[x1][i].size()) {
					rep(k, to[x2][i].size()) {
						long long newcost = cost + 2;
						int next0 = min(to[x1][i][j], to[x2][i][k]);
						int next1 = max(to[x1][i][j], to[x2][i][k]);
						//cout << next0 << " " << next1 << endl;
						if (newcost < dp[next0][next1]) {
							//cout << next0 << "push" << next1 << endl;
							dp[next0][next1] = newcost;
							q.push({ newcost,{next0,next1} });
						}
					}
				}
			}
		}
	}
	if (ans == LINF) {
		ans = -1;
	}
	cout << ans << endl;
	return 0;
}
#include <bits/stdc++.h>
// #include <atcoder/all>
// #include "icld.cpp"
using namespace std;
using ll = long long int;
using vi = vector<int>;
using si = set<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using ss = string;
using db = double;
template<typename T> using minpq = priority_queue <T,vector<T>,greater<T>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
#define V vector
#define P pair<int,int>
#define PLL pair<ll,ll>
#define rep(i,s,n) for(int i=(s);i<(int)(n);i++)
#define rev(i,s,n) for(int i=(s);i>=(int)(n);i--)
#define reciv(v,n) vll (v)((n)); rep(i,0,(n))cin>>v[i]
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ci(x) cin >> x
#define cii(x) ll x;cin >> x
#define cci(x,y) ll x,y;cin >> x >> y
#define co(x) cout << x << endl
#define pb push_back
#define eb emplace_back
#define rz resize
#define pu push
#define sz(x) int(x.size())
#define vij v[i][j]
// ll p = 1e9+7;
// ll p = 998244353;
// n do -> n*pi/180
#define yn cout<<"Yes"<<endl;else cout<<"No"<<endl
#define YN cout<<"YES"<<endl;else cout<<"NO"<<endl
template<class T>void chmax(T &x,T y){x=max(x,y);}
template<class T>void chmin(T &x,T y){x=min(x,y);}

int main(){
  cci(x,y);
  cii(z);
  int ans=0;
  rev(i,2e6,0){
    if(z*y>x*i){
      ans=i;
      break;
    }
  }

  co(ans);
}