← 返回题目
题库练习 最少交通费
← 上一题 下一题 →

A71330 | 最少交通费

来源编程题
时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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

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

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

输入格式

第 1 行有 2 个整数 n 和 m（1≤n,m≤10^5）

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

输出格式

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

输入输出样例

输入 #1
3 4
1 2 1
1 3 3
2 3 1
1 1 2
输出 #1
2
C++ 编辑器
输入
输出