Description

现有一 $n$ 个点，$m$ 条边的有有向图。起点为 $1$，终点为 $n$。

求 $1$ 到 $n$ 的最短路径长度及数量。

答案可能会很大，请对 $1E9+7$ 取模

两个不同的最短路方案要求：路径长度相同（均为最短路长度）且最短路经过的点的编号序列不同。

Input Format

第一行输入两个整数 $n$，$m$ ($1<n\le 2000,1<m\le n\times (n-1)$)

接下来 $m$ 行

每行三个整数 $u$，$v$，$w$，($1\le u,v\le n,1\le w\le w$)表示从 $u$ 点到 $v$ 有一条边权为 $w$ 的单向边

题目保证有解

题目保证没有重边和自环

Output Format

输出两个整数 $dis$，$sum$ 分别表示最短路径长度和数量

5 4
1 5 4
1 2 2
2 5 2
4 1 1

4 2

Source

Online Judge http://127.0.0.1