如果你用了分层图，并且做法是 $f_{i,j}$ 代表到达第 $i$ 个点并且最后一条边颜色是 $j$ 的最小代价。

别看这个东西只有 $O(n+m)$ 个点，如果不经过优化边数可以达到 $O(n^2)$。

原理是菊花图（test45）。
具体：

1 2 1
1 3 2
1 4 3
1 5 4
1 6 3
1 7 4
...

$1$ 号点先访问了 $2$ ~ $n$ 号点，第 $i \in [2,n]$ 个点被更新了 $f_{i,i-1}$。

然后，$2$ ~ $n$ 号点反过来更新 $1$ 号点，使得对于 $i \in [2,n]$，$f_{1,i}$ 都被更新了状态并加入队列。

然后所有的 $f_{1,i}$ 状态又都会反过来更新 $1$ ~ $n$ 号点，复杂度卡到 $O(n^2)$