题目背景

Kangkang 拿到了老爷爷给的钱，他在路上漫无目的的走着，突然，他听到了路边人谈论的一个城市——北京，他们说那里的房价十分“便宜”，于是我们的主人公 Kangkang 便想到达北京。

题目描述

每一条路都设有一个收费站，每个收费站都会收取不等的费用，求从 Kangkang 所在地 (点 $1$) 到达北京 (点 $n$) 的最小花费。

简单题意

给出一个带权值有向图，请输出从点 $1$ 到点 $n$ 的最小花费。

输入格式

首先输入两个数，$n$ 和 $q$，分别代表了有 $n$ 个城市和 $q$ 条边。

接下来 $q$ 行，每行 $3$ 个整数，$u,v,w$，代表一条从城市 $u$ 到城市 $v$ 费用为 $w$ 的路。

输出格式

输出最小花费，如果不能到达北京，请输出 -1。

样例 #1

样例输入 #1

3 2
1 2 2
2 3 2

样例输出 #1

4

提示

样例为上图，最小花费为 $2+2=4$。

对于 $100\%$ 的数据，$n,q \leq 10^3$。