Great Voyage

【题目背景】

船舷无声刻下 却能留住浪花

风唤醒一天 日记自行翻篇 

地图又一片 等待新的探险 

旅途中的一切 在远处天边

【题目描述】

给定一张 $n$ 个点 $m$ 条边的有向图，第 $i$ 条边从点 $u_i$ 连接到点 $v_i$，其边权为 $w_i$。

对于一条路径，假设经过的边的边权依次为 $w_{x_1}, w_{x_2},\cdots, w_{x_s}$，那么需要消耗的代价为 $\max\limits_{i=1}^s i \cdot w_{x_i}$。例如，如果经过的边的边权依次为 $2, 3, 1$，则代价为 $\max\{1 \times 2, 2 \times 3, 3 \times 1\} = 6$。

现在，你要找到一条从 $1$ 号点走到 $n$ 号点的路径，使得这条路径所消耗的代价最小。

【输入格式】

输入的第一行包含两个整数 $n, m$，描述有向图中的点数与边数。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，描述一条边。点的编号为 $1 \sim n$ 中的正整数。

图中可能存在重边与自环。

【输出格式】

一个整数，表示答案。

【样例输入 1】

3 3
1 2 2
1 3 6
2 3 4

【样例输出 1】

6

【样例输入 2】

9 11
1 2 1
1 3 8
1 4 6
1 8 17
2 4 1
2 5 3
2 8 2
4 6 7
4 7 2
6 8 1
8 9 3

【样例输出 2】

9

【样例说明】

$1\to 3$ 有两条路径：$1\to 2\to 3$，代价 $\max\{1\times 2, 2\times 4\} = 8$；$1\to 3$，代价 $1\times 6 = 6$。

本来这里应该有个大样例的，然而 COGS 传不上来，只能当锻炼大家的对拍能力了。

【数据规模与约定】

对于 $20\%$ 的数据，$n,m \le 20$。

对于 $50\%$ 的数据，$n,m \le 100$，$w_i \le 10^4$。

对于 $80\%$ 的数据，$n,m \le 2\,000$。

对于 $100\%$ 的数据，$2 \le n \le 3 \times 10^5$，$1 \le m \le 3 \times 10^5$，$1 \le w_i \le 10^9$，至少有一条从 $1$ 号点到 $n$ 号点的路径。

【来源】

lgc。