AT_abc197_f [ABC197F] Construct a Palindrome

有一个包含 $N$ 个顶点和 $M$ 条边的连通无向图（不一定是简单图）。 第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，并且上面写有一个字母 $C_i$。 你可以从顶点 $1$ 走到顶点 $N$，路径上可以多次经过同一条边或顶点。 请任选一条这样的路径，将经过的边上的字母按顺序排列，得到一个字符串。 请判断是否存在使得该字符串为回文串的路径。如果存在，求所有可能的回文串中最短的长度；如果不存在，输出 $-1$。

输入以如下格式从标准输入读入。 > $N$ $M$ > $A_1$ $B_1$ $C_1$ > $A_2$ $B_2$ $C_2$ > $A_3$ $B_3$ $C_3$ > $\vdots$ > $A_M$ $B_M$ $C_M$

如果可以构造出回文串，输出所有可能回文串长度的最小值；否则输出 $-1$。

## 限制条件 - $2 \leq N \leq 1000$ - $1 \leq M \leq 1000$ - $1 \leq A_i \leq N$ - $1 \leq B_i \leq N$ - $C_i$ 是小写英文字母 - 给定的图是连通的 ## 样例解释 1 按边 $1, 2, 3, 1, 2, 4, 5, 6, 7, 8$ 的顺序经过，得到的字符串为 `abcabbacba`，这是一个回文串。无法构造更短的回文串，因此答案为 $10$。 ## 样例解释 2 按边 $2, 3, 4, 5, 5$ 的顺序经过，可以得到字符串 `aabaa`，这是一个回文串。注意可以多次经过同一条边或顶点。 ## 样例解释 3 无法构造出回文串。 由 ChatGPT 4.1 翻译