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

Description

题目描述

有 n 个 城市，从1到 n 给他们编号，它们之间由一些单向道路（即一条道路只能从一个方向走向另一个方向，反之不行）相连，每条路还有一个花费 c(i) ，表示通过第i条边需要花费 c(i) 的时间。

现在要求从 1 走到 n 。问最少需要多少时间。

Input Format

输入格式

第一行两个整数 n 和 m，表示有多少个城市和多少条道路。

接下来 m 行，每行两个整数 u 、v 、c ，即有一条从 u 到 v 需要花费时间 c 的道路。

Output Format

输出格式

一行一个整数，即从 1 到 n最少需要多少时间。

4 5
1 2 20
1 3 10
3 2 5
2 4 7
3 4 15​

22​

Hint

100% 的数据，$1≤n,m≤1000001$