2379 - 最少交通费
题目描述
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 。
样例
输入
3 4 1 2 1 1 3 3 2 3 1 1 1 2
输出
2
标签
