题目描述

给定一个有向图，图里有 $n$ 个点。$m$ 条单向正权边，求解从 $1$ 号点到 $n$ 号点的最短距离。

输入格式

第一行包含整数 $n$ 和 $m。$

接下来 $m$ 行每行包含三个整数 $a, b, c$ 表示存在一条从 $a$ 点 到 $b$ 点 且长度为 $c$ 的一条边。

输出格式

输出一个整数，表示从 $1$ 号点到 $n$ 号点的最短距离。

如果路径不存在，则输出 $−1。$

数据范围

$1 \leq n \leq 500.$

$1 \leq m \leq 10000.$

$1 \leq c \leq 10000.$

输入样例：

3 3
1 3 209
1 1 88
1 3 449

输出样例：

209