You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

“RP 餐厅” 的员工素质就是不一般，在齐刷刷的算出同一个电话号码之后，就准备让 HZH,TZY 去送快餐了，他们将自己居住的城市画了一张地图，已知在他们的地图上，有 $N$ 个地方，而且他们目前处在标注为 “1” 的小镇上，而送餐的地点在标注为 “N” 的小镇。（有点废话）除此之外还知道这些道路都是单向的，从小镇 $I$ 到 $J$ 需要花费 $D[I, J]$ 的时间，为了更高效快捷的将快餐送到顾客手中，他们想走一条从小镇 $1$ 到小镇 $N$ 花费最少的一条路，但是他们临出发前，撞到因为在路上堵车而生气的 FYY，深受启发，不能仅知道一条路线，万一。。。于是，他们邀请 FYY 一起来研究起了下一个问题：这个最少花费的路径有多少条？

输入格式

输入文件第一行为两个空格隔开的数 $N, E$，表示这张地图里有多少个小镇及有多少边的信息。

下面 $E$ 行，每行三个数 $I, J, C$，表示从 $I$ 小镇到 $J$ 小镇有道路相连且花费为 $C$。（注意，数据提供的边信息可能会重复，不过保证 $I \ne J$，$1 \leq I, J\leq N$）。

输出格式

输出文件包含两个数，分别是最少花费和花费最少的路径的总数。保证花费最少的路径的总数不超过 $2^{30}$。

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

若城市 $N$ 无法到达则只输出一个 No answer。

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

4 2

提示

对于 $30\%$ 的数据 $N\leq 20$；

对于 $100\%$ 的数据 $1\leq N\leq 2000$，$0\leq E\leq N\times (N-1)$，$1\leq C\leq 10$。