有 n 个 城市，从1到 n 给他们编号，它们之间由一些单向道路（即一条道路只能从一个方向走向另一个方向，反之不行）相连，每条路还有一个花费 c(i) ，表示通过第i条边需要花费 c(i) 的时间。
现在要求从 1 走到 n 。问最少需要多少时间。
第一行两个整数 n 和 m，表示有多少个城市和多少条道路。
接下来 m 行，每行两个整数 u 、v 、c ，即有一条从 u 到 v 需要花费时间 c 的道路。
一行一个整数，即从 1 到 n 最少需要多少时间。
输入样例
4 5 1 2 20 1 3 10 3 2 5 2 4 7 3 4 15
输出数据
22
70% 的数据，1≤n,m≤1000
100% 的数据，1≤n,m≤10000