5008: Shortest Path最短路径

In Ancient Berland there were n cities and m two-way roads of equal length. The cities are numbered with integers from 1 to n inclusively. According to an ancient superstition, if a traveller visits three cities a_i, b_i, c_i in row, without visiting other cities between them, a great disaster awaits him. Overall there are k such city triplets. Each triplet is ordered, which means that, for example, you are allowed to visit the cities in the following order: a_i, c_i, b_i. Vasya wants to get from the city 1 to the city n and not fulfil the superstition. Find out which minimal number of roads he should take. Also you are required to find one of his possible path routes.
在古伯兰，有n个城市和m条等长的双向道路。城市用从 1 到 n 的整数编号。根据古老的迷信，如果旅行者访问三个城市ai,bi,ci在他们之间没有访问其他城市的情况下，一场巨大的灾难在等待着他。总的来说，有k这样的城市三胞胎。每个三胞胎都是有序的，这意味着，例如，您可以按以下顺序访问城市：一个ai,bi,ci.瓦夏想从城市 1 到城市 n 而不是实现迷信。找出他应该走哪条最少的道路。此外，您还需要找到他可能的路径路线之一。