#include using namespace std; int main(){ int N, M; cin >> N >> M; vector>> E(N); for (int i = 0; i < M; i++){ int A, B; char C; cin >> A >> B >> C; A--; B--; E[A].push_back(make_tuple(C, i, B)); E[B].push_back(make_tuple(C, i, A)); } vector> d(27, vector(N, -1)); vector> pv(27, vector(N, -1)); vector> pe(27, vector(N, -1)); vector> ps(27, vector(N, -1)); vector> pc(27, vector(N, -1)); queue> Q; for (int i = 0; i < 26; i++){ d[i][0] = 0; Q.push(make_pair(i, 0)); } while (!Q.empty()){ int s = Q.front().first; int v = Q.front().second; Q.pop(); for (auto e : E[v]){ char c = get<0>(e); if (!(v == 0 && s != c - 'a')){ int w = get<2>(e); int s2 = s; if (s != c - 'a'){ s2 = 26; } if (d[s2][w] == -1){ d[s2][w] = d[s][v] + 1; pv[s2][w] = v; pe[s2][w] = get<1>(e); ps[s2][w] = s; pc[s2][w] = c; Q.push(make_pair(s2, w)); } } } } if (d[26][N - 1] == -1){ cout << -1 << endl; } else { string S; vector ans; int c = N - 1; int s = 26; while (c != 0 || s == 26){ S += pc[s][c]; ans.push_back(pe[s][c]); int c2 = pv[s][c]; int s2 = ps[s][c]; c = c2; s = s2; } reverse(S.begin(), S.end()); reverse(ans.begin(), ans.end()); string S2 = S; reverse(S2.begin(), S2.end()); if (S == S2){ while (S.size() + 2 <= N * 2){ char ch = pc[26][N - 1]; S += ch; S += ch; ans.push_back(pe[26][N - 1]); ans.push_back(pe[26][N - 1]); } S2 = S; reverse(S2.begin(), S2.end()); } if (S == S2){ cout << -1 << endl; } else { int k = ans.size(); cout << k << endl; for (int i = 0; i < k; i++){ cout << ans[i] + 1 << endl; } } } }