题目描述

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

输入格式

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

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

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

• 1. 初始化${x=y=z=0}$。
• 2. 重复以下过程$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);
  • 则有一条从${a}$到${b}$的，长度为${1e8-100*a}$的有向边。

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

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

输出格式

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

样例

输入样例

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

输出样例

2

提示

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