#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define lowbit(x) (x&-x)
#define reg register
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=998244353;
const LL jzm=2333;
const int iv2=499122177;
const double Pi=acos(-1.0);
typedef pair<int,int> pii;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int n,k,head[MAXN],tot,lim,hei[MAXN],sum;
struct edge{int to,nxt;}e[MAXN<<1];
void addEdge(int u,int v){e[++tot]=(edge){v,head[u]};head[u]=tot;}
void dosaka(int u,int fa){
	int mx1=0,mx2=0;if(!head[u]){hei[u]=0;return ;}
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;if(v==fa)continue;dosaka(v,u);
		if(hei[v]>=0)mx1=max(mx1,hei[v]+1);
		else mx2=max(mx2,-hei[v]-1);
	}
	if(mx2>mx1)hei[u]=-mx2;else hei[u]=mx1;
	if(hei[u]>=lim||(u==1&&hei[u]>=0))hei[u]=-lim-1,sum++;
	//printf("dosaka%d:%d\n",u,hei[u]);
}
bool check(int mid){
	for(int i=1;i<=n;i++)hei[i]=0;
	lim=mid;sum=0;dosaka(1,0);return sum<=k;
}
signed main(){
	read(n);read(k);
	for(int i=1;i<n;i++){
		int u,v;read(u);read(v);
		addEdge(u,v);addEdge(v,u);
	}
	int l=1,r=n;if(k>=n){puts("0");return 0;}
	while(l<r){int mid=l+r>>1;if(check(mid))r=mid;else l=mid+1;}
	printf("%d\n",l);
	return 0;
}

/*                                                       
  /^--^\                                                 
  \____/                                                 
 /      \ _____  _ __  __ ____  _     ____   ____  _____ 
|        || ()_)| |\ \/ /| ===|| |__ / (__` / () \|_   _|
 \__  __/ |_|   |_|/_/\_\|____||____|\____)/__/\__\ |_|  
|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|
| | |\ \| | | | | | | | | | | | | | | | | | | | | | | | |
#####/ /#################################################
| | |\/ | | | | | | | | | | | | | | | | | | | | | | | | |
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|*/
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int ll //__int128
#define double long double
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define For(i,a,b)    for(int i=a;i<=b;i++)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define Forr(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)
#define LO(x) (x&(-x))

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(1000000007)
#define INF (int)(1e12)
#define EPS (1e-7)

#ifdef NYAOWO
#define debug(...) do{\
	cerr << __LINE__ <<\
	" : ("#__VA_ARGS__ << ") = ";\
	_OUT(__VA_ARGS__);\
	cerr << flush;\
}while(0)
template<typename T> void _OUT(T x) { cerr << x << "\n"; }
template<typename T,typename...I>
void _OUT(T x,I ...tail) { cerr << x << ", "; _OUT(tail...); }
inline void USACO(const string &s) { cerr<<"USACO: "<<s<<"\n"; }
#else
#define debug(...)
inline void USACO(const string &s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
#endif
inline void NYA(){ ios::sync_with_stdio(false); cin.tie(0); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
inline int gcd(int a,int b) { return __gcd(a,b); }
inline int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p,const int &mod){
	int ans=1;
	while(p){
		if(p&1) ans=ans*b%mod;
		p/=2; b=b*b%mod;
	}
	return ans;
}
int fpow(int b,int p) { return fpow(b,p,MOD); }
template<typename T> inline void chmin(T &_a,const T &_b) { if(_b<_a) _a=_b; }
template<typename T> inline void chmax(T &_a,const T &_b) { if(_b>_a) _a=_b; }

int dis[1010][1010];
vector<int> adj[1010][26];

int32_t main(){
	NYA();
	//nachoneko so cute >/////<
	int n,m; cin>>n>>m;
	memset(dis,-1,sizeof(dis));
	priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> pq;
	//pair( dist , pair( s,t ) ) where s<=t
	For(i,1,n) pq.emplace(0,mkp(i,i));
	while(m--){
		int a,b; cin>>a>>b;
		char ch; cin>>ch;
		adj[a][ch-'a'].eb(b);
		adj[b][ch-'a'].eb(a);
		if(a>b) swap(a,b);
		pq.emplace(1,mkp(a,b));
	}
	while(!pq.empty()){
		int d=pq.top().F;
		int s=pq.top().S.F;
		int t=pq.top().S.S;
		pq.pop();
		if(dis[s][t]!=-1) continue;
		dis[s][t]=d;
		For(ch,0,25){
			for(auto &a:adj[s][ch]) for(auto &b:adj[t][ch]){
				int x=min(a,b),y=max(a,b);
				if(dis[x][y]==-1) pq.emplace(d+2,mkp(x,y));
			}
		}
	}
	cout<<dis[1][n]<<"\n";
	return 0;
}