#include <bits/stdc++.h>

using namespace std;

#define MS(a, b) memset(a, b, sizeof(a))
#define REP(a, b, c) for (register int a = b, _n = c; a <= _n; ++a)
#define DREP(a, b, c) for (register int a = b, _n = c; a >= _n; --a)
#define FOR(a, b, c) for (register int a = b, _n = c; a < _n; ++a)
#define EREP(a, b) for (register int a = head[b]; a; a = edge[a].nxt)

inline int rd() {
    int x = 0; char c = getchar(); bool f = 0;
    while (c < '0' && c != '-') c = getchar();
    if (c == '-') f = 1, c = getchar();
    while (c >= '0') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}

const int SIZE = 2e5 + 100;

int n; 

int head[SIZE], ecnt;
struct Edge {
	int v, nxt;
} edge[SIZE << 1];
void Add_Edge (int u, int v) {
	edge[++ecnt] = (Edge) { v, head[u] };
	head[u] = ecnt;
}

int dep[SIZE], F[SIZE];
int mx[SIZE][2];
int Len = -1, A, B;
void dfs (int u, int fa) {
	F[u] = fa;
	dep[u] = dep[fa] + 1;
	mx[u][0] = mx[u][1] = u;
	EREP (i, u) {
		int v = edge[i].v;
		if (v == fa) continue;
		dfs(v, u);
		if (dep[mx[v][0]] > dep[mx[u][0]])
			mx[u][1] = mx[u][0], mx[u][0] = mx[v][0];
		else if (dep[mx[v][0]] > dep[mx[u][1]])
			mx[u][1] = mx[v][0];
	}
	if (dep[mx[u][0]] + dep[mx[u][1]] - 2 * dep[u] > Len) {
		Len = dep[mx[u][0]] + dep[mx[u][1]] - 2 * dep[u];
		A = mx[u][0];
		B = mx[u][1];
	}
}
bool mark[SIZE];
int E;
int ans[SIZE];
void D (int u, int fa) {
	++E;
	ans[u] = E;
	EREP (i, u) {
		int v = edge[i].v;
		if (v == fa) continue;
		if (!mark[v]) D(v, u);
	}
	EREP (i, u) {
		int v = edge[i].v;
		if (v == fa) continue;
		if (mark[v]) D(v, u);
	}
	++E;
}

void _main () {
	n = rd();
	FOR (i, 1, n) {
		int u = rd(), v = rd();
		Add_Edge(u, v);
		Add_Edge(v, u);
	}
	dfs(1, 0);
	int T = A;
	while (A != B) {
		if (dep[A] < dep[B]) swap(A, B);
		mark[A] = 1;
		A = F[A];
	} mark[A] = 1;
	D(T, 0);
	REP (i, 1, n) printf ("%d ", ans[i]);
}

int main () {
#ifdef LOCAL
	freopen("in.txt", "r", stdin);
#endif
	_main();
	return 0;
}

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

const int64_t MOD = 1e9 + 7;
const int64_t MOD2 = 998244353;
const int INF = 2e9;
const long long inf = 1LL<<60;
template<typename T>
bool chmin(T& x, const T& y){
  if(x <= y) return false;
  x = y;
  return true;
}
template<typename T>
bool chmax(T& x, const T& y){
  if(x >= y) return false;
  x = y;
  return true;
}
void Dijkstra(int s, vector<vector<pair<long long, long long>>> &G, vector<long long> &d) {
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;
  d[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    auto k = q.top();
    q.pop();
    if (d[k.second] != k.first) continue;
    for (auto p : G[k.second]) {
      long long next = k.first + p.second;
      if (chmin(d[p.first], next)) q.push({next, p.first});
    }
  }
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<long long> a(m), b(m);
  vector<char> c(m);
  vector<vector<pair<long long, long long>>> G(n*n+1);
  for (int i=0; i<m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--;
    G[a[i]*n+b[i]].push_back({n*n, 1});
    G[b[i]*n+a[i]].push_back({n*n, 1});
  }
  for (int i=0; i<m; i++) {
    for (int j=0; j<m; j++) {
      if (c[i] == c[j]) {
        G[a[i]*n+a[j]].push_back({b[i]*n+b[j], 2});
        G[b[i]*n+b[j]].push_back({a[i]*n+a[j], 2});
        G[a[i]*n+b[j]].push_back({b[i]*n+a[j], 2});
        G[b[i]*n+a[j]].push_back({a[i]*n+b[j], 2});
      }
    }
  }
  /*
  vector<vector<pair<int, int>>> alp(26);
  for (int i=0; i<m; i++) {
    int a, b;
    char c;
    cin >> a >> b >> c;
    a--; b--;
    alp[c - 'a'].push_back({a, b});
    alp[c - 'a'].push_back({b, a});
  }*/
  /*
  for (int i=0; i<26; i++) {
    for (int j=0; j<(int)alp[i].size(); j++) {
      for (int k=j+1; k<(int)alp[i].size(); k++) {
        long long a = alp[i][j].first, b = alp[i][j].second;
        long long c = alp[i][k].first, d = alp[i][k].second;
        G[a*n+d].push_back({b*n+c, 2});
        G[b*n+c].push_back({a*n+d, 2});
        G[a*n+c].push_back({b*n+d, 2});
        G[b*n+d].push_back({a*n+c, 2});
      }
    }
  }*/
  for (int i=0; i<n; i++) {
    G[i*n+i].push_back({n*n, 0});
  }/*
  for (int i=0; i<26; i++) {
    for (auto p : alp[i]) {
      G[p.first*n+p.second].push_back({n*n, 1});
      G[p.second*n+p.first].push_back({n*n, 1});
    }
  }*/
  vector<long long> d(n*n+1, inf);
  Dijkstra((long long)(n-1), G, d);
  if (d[n*n] >= inf) cout << -1 << endl;
  else cout << d[n*n] << endl;
}
