先放 hack 数据：

8 9
1 6 7 8
1 2 5
2 3 3
3 4 4
4 5 3
5 6 5
7 3 4
7 5 4
2 8 3
4 8 3

正确输出：

6

此数据图示如下：

第一条最短路为 $1-2-8-4-5-6$，第二条为 $7-5-4-8$ 时，公共路径长度最大，为 $6$（本题中只考虑最短路径的公共长度，不考虑同向或相向）。

被 hack 题解（共 $12$ 篇）：

https://www.luogu.com.cn/blog/user29936/solution-p2149 输出 $9$。

https://www.luogu.com.cn/blog/chdy/solution-p2149 输出 $3$。

https://www.luogu.com.cn/blog/skylee/solution-p2149 输出 $9$。

https://www.luogu.com.cn/blog/user11280/solution-p2149 输出 $9$。

https://www.luogu.com.cn/blog/xxwang/elaxia-di-lu-xian 输出 $9$。

https://www.luogu.com.cn/blog/pleasun/p2149-sdoi2009elaxia-di-lu-xian-ti-xie 输出 $9$。

https://www.luogu.com.cn/blog/Atalod/solution-p2149 输出 $9$。

https://www.luogu.com.cn/blog/Izayoimiku9/solution-p2149 输出 $9$。

https://www.luogu.com.cn/blog/DanKuroto/solution-p2109 输出 $9$。

https://www.luogu.com.cn/blog/FrigidPigeon/solution-p2149 输出 $9$。

https://www.luogu.com.cn/blog/wqt1600639146/luo-gu-2149-zui-zhang-gong-gong-lu-jing-post 输出 $9$。

https://www.luogu.com.cn/blog/signal/solution-p2149 输出 $9$。