I. Dijkstra II

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个有向图，图里有 $n$ 个点。 $m$ 条单向正权边，求解从 $1$ 号点到 $n$ 号点的最短距离；

输入格式

第一行包含整数 $n$ 和 $m；$

接下来 $m$ 行每行包含三个整数 $a, b, c$ 表示存在一条从 $a$ 点到 $b$ 点且长度为 $c$ 的一条边；

输出格式

输出一个整数，表示从 $1$ 号点到 $n$ 号点的最短距离；

如果路径不存在，则输出 $−1；$

数据范围

$1 \leq n \leq 2\times 10^5.$

$1 \leq m \leq 2\times 10^5.$

$1 \leq c \leq 10000.$

输入样例：

输出样例：

校内专属ACM-ICPC测试