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.

题目背景

翻译自 CSES-1202 题。

题目描述

你将从 Syrjälä 城市飞往 Lehmälä 城市。你想回答以下几个问题：

1. 最短价格的航线是多少？
2. 有多少条最短价格的航线？（结果对 $10^9+7$ 取模）
3. 在最短价格的航线上，最少需要多少次航班？
4. 在最短价格的航线上，最多需要多少次航班？

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示城市的数量和航班的数量。城市编号为 $1,2,…,n$，其中城市 $1$ 是 Syrjälä，城市 $n$ 是 Lehmälä。

接下来的 $m$ 行，每行包含三个整数 $a$、$b$ 和 $c$：表示有一条从城市 $a$ 到城市 $b$ 的单向航班，价格为 $c$。

你可以假设从 Syrjälä 到 Lehmälä 存在至少一条航线。

输出格式

输出四个整数，分别是：

1. 最短价格的航线价格；
2. 最短价格的航线的数量（对 $10^9+7$ 取模）；
3. 在最短价格航线上所需的最少航班数；
4. 在最短价格航线上所需的最多航班数。

样例

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

5 2 1 2

说明/提示

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2 \cdot 10^5$；

$1 \leq a,b \leq n$；

$1 \le c \le 10^9$。