#include<bits/stdc++.h>
typedef long long ll;
//#define ll long long
#define int long long
//#define ull unsigned long long
//#define PI pair<int,int>
//#define PII pair<int,PI>
//#define PI pair<ll,int>
//#define endl "\n"
using namespace std;
const int maxm=2e3+5;

const int p=1e4;
int read(){
    string s;cin>>s;
    int t=4;
    int f=0;
    int ans=0;
    for(auto i:s){
        if(i=='.'){
            f=1;
            continue;
        }else{
            ans=ans*10+(i-'0');
            if(f)t--;
        }
    }
    while(t){
        ans=ans*10;
        t--;
    }
    return ans;
}
signed main(){
//    ios::sync_with_stdio(0);
    //
    int X=read();
    int Y=read();
    int R=read();
    //定义横坐标左右边界
    int lc=X-R;
    int rc=X+R;
    while(lc%p)lc++;
    while(rc%p)rc--;
    //定义上下界指针
    int up=Y,down=Y;
    while(up%p)up++;//取整
    while(down%p)down--;
    //
    int ans=0;
    for(int i=lc;i<=rc;i+=p){//枚举横坐标
        int ix=abs(X-i);
        //
        while(ix*ix+(up-Y)*(up-Y)>R*R)up-=p;//up下移
        while(up<=Y||ix*ix+(up-Y)*(up-Y)<=R*R)up+=p;//up上移
        //
        while(ix*ix+(Y-down)*(Y-down)>R*R)down+=p;//down上移
        while(down>=Y||ix*ix+(Y-down)*(Y-down)<=R*R)down-=p;//down下移
        //
        int add=(up-down)/p-1;
        if(add>0)ans+=add;
    }
    cout<<ans<<endl;
    return 0;
}
/*

*/

#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
//#include<atcoder/all>
//using namespace atcoder;

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N, M;
	cin >> N >> M;

	int A[1001], B[1001];
	char C[1001];
	rep(i, M) {
		cin >> A[i] >> B[i] >> C[i];
		A[i]--;
		B[i]--;
	}
	vector<int> E[1000010];
	rep(i, M) rep(j, M) {
		if (C[i] != C[j]) continue;
		if (i == j) continue;

		E[A[i] * N + A[j]].pb(B[i] * N + B[j]);
		E[A[i] * N + B[j]].pb(B[i] * N + A[j]);
		E[B[i] * N + A[j]].pb(A[i] * N + B[j]);
		E[B[i] * N + B[j]].pb(A[i] * N + A[j]);
	}

	int D[1000100] = {};
	rep(i, N* N) D[i] = 1e9;

	queue<int> que;
	que.push(N - 1);
	D[N - 1] = 0;
	while (que.size()) {
		int u = que.front();
		que.pop();

		for (auto to : E[u]) {
			if (D[to] < 1e8) continue;
			chmin(D[to], D[u] + 1);
			que.push(to);
		}
	}

	//if (D[(N - 1) * N] > 1e8) co(-1);
	//else co(D[(N - 1) * N]);

	int kotae = 1e9;
	rep(i, N) chmin(kotae, D[i * N + i] * 2);
	rep(i, M) chmin(kotae, D[A[i] * N + B[i]] * 2 + 1);
	rep(i, M) chmin(kotae, D[B[i] * N + A[i]] * 2 + 1);

	if (kotae > 1e8) co(-1);
	else co(kotae);

	Would you please return 0;
}