2379 - 最少交通费

题目描述

Mar 星球上共有 n 个城市(编号为 1 \sim n),城市之间为了方便交通修建了 m 条单向高速公路。

有些公路是为了交通方便连接了 2 个不同的城市,有些公路是为了观光方便,从一个城市出发最后还会回到该城市。两个城市之间、以及从本市出发回本市的道路都可能有多条。

作为交通部新来的程序员,你接到了一个第一个任务:已知所有道路起止点以及走该条路需要花的过路费,计算出从 1 号城市到 n 号城市的最低花费?

输入

1 行有 2 个整数 nm1≤n,m≤10^5

接下来 m 行,每行有 3 个整数 uvp,表示从有一条道路从 u 市连到 v 市,走该条路需要花费 p 元。(1≤ u,v ≤n1≤ p ≤10^4)。

输出

输出一个整数,代表从 1 号城市到 n 号城市的最少交通费。如果根据给定的数据发现,从 1 号城市无法到达 n 号城市,请输出 -1

样例

输入

3 4
1 2 1
1 3 3
2 3 1
1 1 2

输出

2
标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题