题目描述

我们有一个连接的无向图，其中包含 $N$ 个顶点和 $M$ 条边，这并不一定是一个简单图。
第 $i$ 条边连接了顶点 $A_i$ 和顶点 $B_i$，并且在上面写有字符 $C_i$。
通过选择从顶点 $1$ 到顶点 $N$ 的路径（可能包含相同的边和顶点），并将路径上边上的字符排列起来，形成一个字符串。
判断这个字符串是否可以是一个回文串。如果可以，找出最小可能的回文串长度。

约束条件

• $2 \le N \le 1000$
• $1 \le M \le 1000$
• $1 \le A_i \le N$
• $1 \le B_i \le N$
• $C_i$ 是小写英文字母。
• 给定的图是连通的。

输入

输入的格式如下，通过标准输入给出：

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $A_3$ $B_3$ $C_3$ $\hspace{15pt} \vdots$ $A_M$ $B_M$ $C_M$

输出

如果可以构成回文串，则打印最小可能的回文串长度；否则，打印 -1。

示例输入 1

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

示例输出 1

10

通过按顺序遍历边 $1, 2, 3, 1, 2, 4, 5, 6, 7, 8$，我们可以构成一个回文串 abcabbacba。
无法构成更短的回文串，因此答案为 $10$。

示例输入 2

4 5
1 1 a
1 2 a
2 3 a
3 4 b
4 4 a

示例输出 2

5

通过按顺序遍历边 $2, 3, 4, 5, 5$，我们可以构成一个回文串 aabaa。
请注意允许相同边和顶点的重复。

示例输入 3

3 4
1 1 a
1 2 a
2 3 b
3 3 b

示例输出 3

-1

我们无法构成回文串。