亚太地区共有 $n$ 座城市，编号从 1 到 $n$。2024 年 ICPC 亚太锦标赛在河内举行，即城市 $n$。

共有 $m$ 条双向道路，编号从 1 到 $m$，连接着某些城市对。第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，双向通行均需花费 $t_i$ 单位时间。每条道路连接不同的城市，且不同的道路连接不同的城市对。

你住在城市 1。你希望通过一系列道路前往城市 $n$ 参加比赛，然后再通过一系列道路返回城市 1。由于走相同的路线很无聊，你希望两次往返的路线不同。如果一条路线所经过的道路集合与另一条路线所经过的道路集合不同，则认为这两条路线不同。

在每次往返中，可以多次经过同一座城市或同一条道路。到达目的地（即城市 1 或城市 $n$）后也可以继续行驶。往返时间为所经过道路的通行时间之和。如果某条道路在往返中被多次经过，则该道路的通行时间也相应地被多次计入。

请确定满足上述要求的两次往返所需的最小总时间，如果无法满足要求，请输出 -1。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 100\,000$; $1 \le m \le \min(\frac{n(n-1)}{2}, 300\,000)$)。接下来的 $m$ 行中，每行包含三个整数。第 $i$ 行包含 $u_i$、$v_i$ 和 $t_i$ ($1 \le u_i < v_i \le n$; $1 \le t_i \le 1000$)。不同的道路连接不同的城市对。

输出格式

输出一个整数，表示满足上述要求的两次往返所需的最小总时间；如果无法满足要求，则输出 -1。

样例

输入 1

3 2
1 2 10
1 3 5

输出 1

30

说明 1

城市和道路如图 J.1 所示。

图 J.1：样例输入 #1 的示意图。

一种使总往返时间最小化的可能方式如下： 从城市 1 前往城市 3，经过道路 2（连接城市 1 和 3）。往返时间为 5。所经过的道路集合为 $\{2\}$。 从城市 3 返回城市 1，经过道路 2，然后经过两次道路 1（连接城市 1 和 2）。往返时间为 $5 + 10 + 10 = 25$。所经过的道路集合为 $\{1, 2\}$。

可以证明，不存在总往返时间更小的方案。

输入 2

4 3
1 2 10
2 3 5
3 4 2

输出 2

-1

说明 2

城市和道路如图 J.2 所示。

图 J.2：样例输入 #2 的示意图。

要从城市 1 前往城市 4 再返回，两次往返都必须经过所有道路。因此，无法满足上述要求。

输入 3

4 4
1 2 3
2 4 2
1 3 3
3 4 4

输出 3

12

输入 4

3 1
1 2 1000

输出 4

-1