import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.datetime; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto G = new Tuple!(int, int, int)[][](N); int[] Cs; foreach (i; 0..M) { auto t = readln.split; auto u = t[0].to!int - 1; auto v = t[1].to!int - 1; auto c = (t[2].to!char - 'a').to!int; G[u] ~= tuple(v, c, i); G[v] ~= tuple(u, c, i); Cs ~= c; } if (Cs.sort().uniq.array.length == 1) { writeln(-1); return; } int mid; foreach (i; 0..N) { if (G[i].map!(t => t[1]).array.sort().uniq.array.length >= 2) { mid = i; break; } } auto H = new Edge!int[][](N); foreach (i; 0..N) foreach (j; G[i]) H[i] ~= Edge!int(j[0], 1); auto path1 = dijkstra!(int, 1<<29)(H, 0, mid); auto path2 = dijkstra!(int, 1<<29)(H, mid, N-1); int[] S; int[] ans1; int[] ans2; foreach (i; 0..path1.length.to!int-1) foreach (j; G[path1[i]]) if (j[0] == path1[i+1]) { S ~= j[1]; ans1 ~= j[2]; } foreach (i; 0..path2.length.to!int-1) foreach (j; G[path2[i]]) if (j[0] == path2[i+1]) { S ~= j[1]; ans2 ~= j[2]; } if (S.dup.sort().uniq.array.length == 1) { foreach (j; G[mid]) if (j[1] != S.front) { ans1 ~= j[2]; ans1 ~= j[2]; break; } } int[] ans = ans1 ~ ans2; if (is_kaibun(S)) { if (path1.length > 1) { ans = [ans.front, ans.front] ~ ans; } else if (path2.length > 1) { ans = ans ~ [ans.back, ans.back]; } } writeln(ans.length); ans.each!(a => (a+1).writeln); } bool is_kaibun(int[] S) { foreach (i; 0..S.length.to!int/2) { if (S[i] != S[S.length.to!int-i-1]) return false; } return true; } struct Edge(T) { int to; T cost; } int[] dijkstra(T, T inf)(const Edge!(T)[][] graph, int start, int goal) { import std.typecons : Tuple, tuple; import std.conv : to; import std.container : BinaryHeap; int n = graph.length.to!int; auto dist = new T[](n); dist[] = inf; dist[start] = 0; int[] prev = new int[](n); prev[] = -1; auto pq = new BinaryHeap!(Array!(Edge!(T)), "a.cost > b.cost"); pq.insert(Edge!(T)(start, 0)); while (!pq.empty) { auto u = pq.front.to; auto cost = pq.front.cost; pq.removeFront; foreach (const e; graph[u]) { auto v = e.to; auto next_cost = cost + e.cost; if (dist[v] <= next_cost) continue; dist[v] = next_cost; prev[v] = u; pq.insert(Edge!(T)(v, next_cost)); } } int[] ans; for (int cur = goal; cur != start; cur = prev[cur]) { ans ~= cur; } ans ~= start; return ans; }