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

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;

double EPS=1e-9;
int INF=1000000005;
long long INFF=1000000000000000005ll;
double PI=acos(-1);
int dirx[8]={ -1, 0, 0, 1, -1, -1, 1, 1 };
int diry[8]={ 0, 1, -1, 0, -1, 1, -1, 1 };
ll MOD = 1000000007;

#define DEBUG fprintf(stderr, "====TESTING====\n")
#define VALUE(x) cerr << "The value of " << #x << " is " << x << '\n'
#define OUT(x) cout << x << '\n'
#define OUTH(x) cout << x << " "
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define READ(x) for(auto &(z):x) cin >> z;
#define FOR(a, b, c) for (int(a)=(b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a)=(b); (a) <= (c); ++(a))
#define FORD(a, b, c) for (int(a)=(b); (a) >= (c); --(a))
#define FORSQ(a, b, c) for (int(a)=(b); (a) * (a) <= (c); ++(a))
#define FORC(a, b, c) for (char(a)=(b); (a) <= (c); ++(a))
#define EACH(a, b) for (auto&(a) : (b))
#define REP(i, n) FOR(i, 0, n)
#define REPN(i, n) FORN(i, 1, n)
#define MAX(a, b) a=max(a, b)
#define MIN(a, b) a=min(a, b)
#define SQR(x) ((ll)(x) * (x))
#define RESET(a, b) memset(a, b, sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PERMUTE next_permutation
#define TC(t) while (t--)
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
#define what_is(x) cerr << #x << " is " << x << '\n'

template<typename T_vector>
void output_vector(const T_vector &v, bool line_break = false, bool add_one = false, int start = -1, int end = -1) {
    if (start < 0) start = 0;
    if (end < 0) end = int(v.size());
    for (int i = start; i < end; i++) {
      cout << v[i] + (add_one ? 1 : 0) << (line_break ? '\n' : i < end - 1 ? ' ' : '\n');
    }
}


void solve() {
    ll n, k; cin >> n >> k;
    vector<pll> v;
    REP(i, n) {
        ll a, b; cin >> a >> b;
        v.pb({a, b});
    }
    SORT(v);
    ll money = k, cur = 0;
    EACH(x, v) {
        if(x.fi > money + cur) {
            cur += money;
            OUT(cur);
            return;
        } else {
            cur += money;
            money = x.se;
        }
    }
    OUT(money + cur);
}
 
int main() {
    FAST_INP;

//    #ifndef ONLINE_JUDGE
//    freopen("input.txt","r", stdin);
//    freopen("output.txt","w", stdout);
//    #endif
 
    // int tc; cin >> tc;
    // TC(tc) solve();
    solve();
    return 0;
}
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <functional>
#include <numeric>
#include <iomanip> 
#include <stdio.h>
//end of libraries
#define lnf 3999999999999999999
#define inf 999999999
#define PI 3.14159265359
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define mkp(a,b) make_pair(a,b)
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())
#define rsz(a,n) a.resize(n)
#define pii pair <int,int>
#define tpii pair <int, pii>
#define rep(i,n) for(int i = 0 ; i < n ; i++) 
#define drep(i,n) for(int i = n-1 ; i >= 0 ; i--)
#define crep(i,x,n) for(int i = x ; i < n ; i++)
#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);

const int max_n = 1500;

using namespace std;
int n,m;
int dp[max_n][max_n];
bool frnd[max_n][max_n];
vector <pii> vc[max_n];

void read() {
	cin >> n >> m;
	rep(i,m) {
		int u,v;
		char ch;
		cin >> u >> v >> ch;
		u--,v--;
		frnd[u][v] = frnd[v][u] = 1;
		vc[u].pb({v,int(ch-'a')});
		vc[v].pb({u,int(ch-'a')});
	}    
}

set <tpii> st;

void rm(int x , int y , int move) {
	if(dp[x][y] < move) return;
	auto ti = st.find({dp[x][y],{x,y}});
	if(ti!=st.end()) st.erase(ti);
	dp[x][y] = move;
	st.insert({move,{x,y}});
}

void solve() {
	
	st.insert({0,{0,n-1}});
	
	rep(i,n) {
		rep(j,n) {dp[i][j] = inf;}
	}
	
	dp[0][n-1] = dp[n-1][0] = 0;

	int ans = inf;

	while(!st.empty()) {
		auto it = st.begin();
		tpii p = *it;
		st.erase(it);
		int move = p.fi;
		pii point = p.se;

		int fv = point.fi , bv = point.se;
		
		if(frnd[fv][bv] == 1) {
			// cerr << fv << " " << bv << "\n";
			ans = min(ans,move*2+1);
		}
		
		for(auto paf : vc[fv]) {
			for(auto pab : vc[bv]) {
				if(paf.se != pab.se) continue;
				if(paf.fi == pab.fi) {ans = min(ans,(move+1)*2); cerr << paf.fi << "\n"; continue;}
				
				rm(paf.fi,pab.fi,move+1);
			}
		}

	}
	cout << (ans==inf?-1:ans) << '\n';
}

int main(){
fcin;
	read();
	solve();	
	

/*
	let f(a,b) be smolest palindrome in which :

	a is connected to 0
	and b is connected to n-1

	and way[a] = way[b]
	then it's just easy to follow up 
	if there is an edge connecting us both then can be also odd length .

*/

    return 0;   
}