#include<bits/stdc++.h>
using namespace std;

int n,m;
int edge[1001][1001];
bool visited[1001][1001];
vector<int> vc[1001][26];

struct PT{
    int st,ed;
    int size;
};

int main(){
    int x,y,sz;
    char c;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>x>>y>>c;
        edge[x][y]=edge[y][x]=1;
        vc[x][c-'a'].push_back(y);
        vc[y][c-'a'].push_back(x);
    }
    bool flag=false;
    queue<PT> q;
    PT temp,in;
    temp.st=1; temp.ed=n; temp.size=0;
    visited[temp.st][temp.ed]=true; 
    q.push(temp);
  	int ans=1e9;
    while(!q.empty()){
        temp=q.front();   
		q.pop();
		x=temp.st; y=temp.ed; sz=temp.size;
        if(edge[x][y]>0||x==y){
            if(x==y) ans=min(ans,sz);
            else ans=min(ans,sz+1);
        }
        for(int t=0;t<26;t++){
            for(auto i:vc[x][t]){
                for(auto j:vc[y][t]){
                    if(visited[i][j]) continue;
                    visited[i][j]=true;
                    temp.st=i; temp.ed=j; temp.size=sz+2;
                    q.push(temp);                   
                }
            }
        }
    }
    if(ans==1e9) cout<<"-1\n";
    else cout<<ans<<'\n';
}
#include <bits/stdc++.h>
using namespace std;
#define la1ee ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main()
{
	la1ee
	int n; cin>>n;
	bool f = false;
	long long int a[n]{}, b[n]{}, c[n]{};
	for(int i=0; i<n; ++i)
	{
		cin>>a[i]>>b[i]>>c[i];
	}
	long long int ans = 1e11;
	//cout<<ans;
	for (int i = 0; i < n; ++i)
	{
		if( (c[i] - a[i]) > 0 )
		{
			ans = min(ans,b[i]);
			f = true;
		}
	}
	if(f) cout<<ans;
	else cout<<"-1";
	return 0;
}