题目描述

$\red N$个点，$\red M$条边的有向图，求点$\red 1$到点$\red N$的最短路（保证存在）。 $\red{1<=N<=1000000，1<=M<=10000000}$

输入格式

第一行两个整数$\red N$、$\red M$，表示点数和边数。

第二行六个整数$\red T$、$\red{rxa}$、$\red{rxc}$、$\red{rya}$、$\red{ryc}$、$\red{rp}$。

前$\red T$条边采用如下方式生成：

• 1. 初始化$\red{x=y=z=0}$。
• 2. 重复以下过程$\red T$次：
  • x=(x*rxa+rxc)%rp;
  • y=(y*rya+ryc)%rp;
  • a=min(x%n+1,y%n+1);
  • b=max(y%n+1,y%n+1);
  • 则有一条从$\red{a}$到$\red{b}$的，长度为$\red{1e8-100*a}$的有向边。

后M-T条边采用读入方式： 接下来$\red {M-T}$行每行三个整数$\red{x}$,$\red{y}$,$\red{z}$，表示一条从$\red x$到$\red y$长度为$\red z$的有向边。

$\red{1<=x,y<=N，0<z,rxa,rxc,rya,ryc,rp<2^{31} }$

输出格式

一个整数，表示$\red{1 \sim N}$的最短路。

样例

输入样例

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

输出样例

2

提示

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