← 返回题目列表

Codeforces · 1302/D

D. 迪杰斯特拉

中文机器翻译题面 查看原题

这是一次不寻常的比赛中的一个不寻常的问题,这里是公告: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