Ac 来到了一个花园，这个花园有 $n$ 个景点，由于花园客流量太大，景点由 $m$ 条单向带权边相连。

Ac 从 $1$ 号节点开始游览花园，出口在 $n$ 号点，但他不希望过快地离开花园，所以他要求至少走一个环，再走到出口。

请你帮他求出他最短的游览时间（即走过的边权总和，重复经过一条边权值应算多次）。

注意，题面中的环指的是至少包含一条边的环。

输入格式

第一行两个正整数 $n$ 和 $m$。

接下来 $m$ 行，每行三个正整数 $u, v, w$，表示一条由 $u$ 指向 $v$ 的权值为 $w$ 的单向边。

输出格式

输出 Ac 最短的游览时间。

如果不能实现，请输出 $−1$。

样例一

input

6 7
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
2 2 3
5 5 2

output

7

explanation

选择 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 5 \rightarrow 6$ 这条路径最优。

样例二

见样例数据下载

样例三

见样例数据下载

限制与约定

对于 $20\texttt{%}$ 的数据，$n \le 10，m \le 30$

对于另外 $10\texttt{%}$ 的数据，$n = m$

对于另外 $10\texttt{%}$ 的数据，$m \ge n$ 且前 $n$ 条边中第 $i$ 条边有 $u = v = i, w = 1$

对于另外 $30\texttt{%}$ 的数据，$n, m \le 300$

对于 $100\texttt{%}$ 的数据，$2 \le n, m \le 3000$，$1 \le u, v \le n，1 \le w \le 2 * 10^9$

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载