#include<bits/stdc++.h>
using namespace std;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
using ll =long long;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,char>>> e(n);
    bool v[1000][1000]={};
    for(int i{},a,b;i<(m);++i){
        char c;
        cin>>a>>b>>c;--a,--b;
        v[a][b]=v[b][a]=true;
        e[a].emplace_back(b,c);
        e[b].emplace_back(a,c);
    }
    using ti = tuple<int,int,int>;
   queue<ti> pq;
    vector<vector<bool>> cc(n,vector<bool>(n,false));
    pq.emplace(0,0,n-1);
    int ans{INT_MAX};


    while(!pq.empty()){
    ll c,i,I;
    tie(c,i,I)=pq.front();pq.pop();
        if(ans<=2*c) break;
        if(i==I){
            chmin(ans, 2*c);
            break;
        }
        if(v[i][I]){
            chmin(ans,2*c+1);
            continue;
        }
        if(cc[i][I]) continue;

        cc[i][I]=true;
        
        for(auto[j,cj]:e[i]) for(auto[J,cJ]:e[I]) if(cj==cJ){
           
            pq.emplace(c+1, j, J);
        }
    }
    cout<<(ans==INT_MAX?-1:ans)<<'\n';
}



// Problem: F - Rook on Grid
// Contest: AtCoder - Panasonic Programming Contest (AtCoder Beginner Contest 186)
// URL: https://atcoder.jp/contests/abc186/tasks/abc186_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = 2e5+7;
int r[N],c[N],tr[N];
vector<int> link[N];
int n,m,k;
inline int lowbit(int x)
{
	return x & -x;
}

int query(int x)
{
	int res = 0;
	for(int i = x;i;i -= lowbit(i))
		res += tr[i];
	return res;
}

void modify(int x,int v)
{
	for(int i = x;i <= m;i += lowbit(i))
		tr[i] += v;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	forn(i,1,n)	r[i] = m + 1;
	forn(i,1,m)	c[i] = n + 1;
	while(k--)
	{
		int x,y;scanf("%d%d",&x,&y);
		c[y] = min(c[y],x);
		r[x] = min(r[x],y);
	}
	
	ll res = 0;
	forn(i,1,m)
	{
		if(c[i] == 1)	break;
		res += c[i] - 1;
	}
	
	forn(i,1,m)	link[c[i]].push_back(i);
	forn(i,1,n)
	{
		if(r[i] == 1)	break;
		res += query(r[i] - 1);
		// cout << query(r[i] - 1) << endl;
		if(i == 1)
		{
			// cout << r[1] << " " << query(7) << endl;
			forn(j,r[1],m)
			{
				modify(j,1);
			}
		}
		else	for(auto j : link[i])	if(j < r[1])	modify(j,1);
	}	
	printf("%lld",res);
    return 0;
}
