乐跑购物

题目限制

1000 ms 256 M

题目描述

$n$ 个城市（编号 $1$ 到 $n$ ）之间有 $m$ 条双向道路，所有城市互相连通。

一群乐跑爱好者，要从城市 $1$ 跑到城市 $n$ ，城市道路上有一些商品在售卖，商品的编号为 $a$ 到 $z$ ，跑步者每经过一条道路，都会购买售卖的商品，他们希望最终将购买的商品按照途经的顺序排在一起组成一个字符 $S$，而 $S$ 是一个回文字符（乐跑的意义所在）。

同时他们也不希望过于劳累，希望在满足上面要求的情况下，路线尽可能的短，问最短需要经过多少条道路（注：可以通过某条道路超过 $1$ 次），图中可能存在自环和重边。

输入格式

第1行：两个数n,m ，表示城市的数量和道路的数量。 后面m行：每行3个数，u,v,w 表示城市 u 到城市v之间存在道路，并且售卖的商品编号为 w。 其中2≤n≤1000,1≤m≤1000。

输出格式

如果无法做到上面的要求，输出-1，否则输出最少经过几条道路。

数据范围

对于15%的数据，$2 \le n \le 10, 1 \le m \le 10$

对于30%的数据，$2 \le n \le 200$

对于100%的数据，$2 \le n \le 1000, 1 \le m \le 1000, 1 \le u,v \le 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