问题 F: 最短回文

给定一个连通的无向图，其中包含 $N$ 个顶点和 $M$ 条边（可能存在自环边和重复边）。每条边连接两个顶点 $A_i$ 和 $B_i$，并且在边上标有字符 $C_i$（小写英文字母）。
我们需要选择从顶点 $1$ 到顶点 $N$ 的路径（可以包含重复的边和顶点），并按照路径上边上的字符顺序形成一个字符串。
我们需要确定这个字符串是否可以构成一个回文串。如果可以构成回文串，则找出可能的最小回文串长度。
回文串是一个正读和反读都相同的字符串。

8 8
1 2 a
2 3 b
1 3 c
3 4 b
4 5 a
5 6 c
6 7 b
7 8 a

10