CF59E Shortest Path

在Ancient Berland有$n$ 座城市和$m$ 条长度相同的双向道路。城市从$1$ 到$n$ 编号。根据一个古老的迷信说法，如果一个旅行者连续访问了$a_i$ 、$b_i$ 、$c_i$ 三座城市而不去拜访其他城市，来自东方的神秘力量将使他遭受巨大的灾害。传说中一共有$k$ 组这样的城市，每个三元组都是有序的，这意味着你可以按照$a_i$ 、$c_i$ 、$b_i$ 这样的方式来访问一组城市而不遭受灾害。Vasya想要从城市$1$ 走到城市$n$ 并且不受到诅咒。请告诉他最短路的长度，并输出一条路线。

无

无