题目描述

$n$ 个点，$m$ 条边的有向图，求点 $1$ 到点 $n$ 的最短路（保证存在）。

输入格式

第一行两个整数 $n$、$m$，表示点数和边数。

第二行六个整数 $t$、$rxa$、$rxc$、$rya$、$ryc$、$rp$。

前 $t$ 条边采用如下方式生成：

1.初始化 $x=y=z=0$。

2.重复以下过程 $T$ 次：

则有一条从 $a$ 到 $b$ 的，长度为 $10^8-100a$ 的有向边。

后 $m-t$ 条边采用读入方式：

接下来 $m-t$ 行每行三个整数 $x,y,z$，表示一条从 $x$ 到 $y$ 长度为 $z$ 的有向边。

输出格式

一个整数，表示 $1-n$ 的最短路。

样例输入

3 3
0 1 2 3 5 7
1 2 1
1 3 3
2 3 1

样例输出

2

提示

请采用高效的堆来优化 Dijkstra 算法。

数据规模与约定

对于 $100\%$ 的数据，$1\leq x,y\leq n$，$0<z,rxa,rxc,rya,ryc,rp<2^31$，$1\leq n\leq 1\times 10^6$，$1\leq m\leq 1\times 10^7$。

题目来源

WC2013营员交流-lydrainbowcat