题目描述

$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