这是一次不寻常的比赛中的一个不寻常的问题,这里是公告:http://codeforces.com/blog/entry/73543
求无向加权图中顶点 $$$1$$$ 和 $$$n$$$ 之间的距离。
输入
第一行包含两个整数 $$$n, m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — 顶点数和边数。
接下来的 $$$m$$$ 行包含边 $$$a_i~b_i~cost_i$$$ 的描述 ($$$1 \leq a_i, b_i \leq n$$$, $$$1 \leq cost_i \leq 10^9$$$)。
循环和多重边?嗯,为什么不呢?
输出
打印一个整数——问题的答案。如果没有路径,则打印$$$-1$$$。
示例
输入 #1
3 3 1 2 5 2 3 1 1 3 7
输出 #1
6