时间限制：1000ms　内存限制：512MB

题目描述

沿海一家航运公司经营着一张港口航线网，网内有 $n$ 个港口，编号 $1$ 到 $n$，港口之间开着 $m$ 条定期航线。每条航线连接两个不同的港口，双向通航，跑一个单程有固定的耗时节数。同一对港口之间有时开着不止一条航线——可能是不同年份开通的，耗时不一定相同；也有个别港口位置偏僻，一条航线都没接上，与主网完全不通。

$1$ 号港是公司的主港，$n$ 号港是最大的货主港，两点之间的货运量占了公司业务的半壁江山。平时货船都走耗时最短的路线，这条主用路线的耗时是调度室人手一份的基本数据。麻烦出在台风季：主用路线上的航线随时可能停航，短则几天，长则半个月。公司的应急预案要求，一旦主用路线中断，货船立刻改走"备用路线"——在所有从 $1$ 号港到 $n$ 号港的走法中，挑出一条严格比主用路线慢、但又慢得最少的路线。换句话说，备用路线的耗时要尽量小，但必须和主用路线的耗时不同，哪怕只多一节也行。

这里"走法"的口径很宽：货船从 $1$ 号港出发，沿航线一段段开，中途经过的港口不限次数，同一条航线跑几个来回也都算数，只要最终抵达 $n$ 号港。所以备选走法其实五花八门——比如在主用路线上多绕一小段折返路，总耗时就会比主用路线多出一点，这种走法同样进入候选。调度室核定预案时，把所有候选走法按耗时排队，耗时最短的若干条走法统统登记为备用路线，条数也要写进预案，以便评估台风季的调度压力。

统计走法条数时，调度室按货船实际经过的航线序列来区分：两种走法只要中途驶过的航线依次列出来不完全相同，就算两种不同的走法。两个港口之间若开着好几条航线，货船经过这对港口时走了哪一条，是算数的——同一段航程，走甲航线和走乙航线，在登记册上是两种走法，哪怕耗时一模一样。每条航线的耗时都是正数，没有不花时间就到的航程；航线网里也特意不修连接同一个港口自身的环线，登记表上每条航线的两端总是两个不同的港口。

这套预案制度是台风季逼出来的。早几年没有备用路线的说法，主用路线一停航，货船就在港里干等，货主天天打电话催。后来公司规定，每年入汛前调度室都要把当年航线网的备用路线重新核定一遍，耗时和条数两项数据一并上报。航线网每年都有变动，新航线开通、旧航线停运，上一年的预案直接作废，必须从头核算。

程老师接到的任务是：根据航线网算出备用路线的耗时，以及达到这一耗时的走法共有多少种。走法种数可能很大，预案表格里只登记它对 $998244353$ 取模的余数。如果 $1$ 号港与 $n$ 号港之间根本不通，预案无从谈起，按格式记两个 $-1$。

输入格式

第一行两个整数 $n, m$，表示港口数量和航线数量。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示一条连接 $u$ 号港与 $v$ 号港的航线，双向通航，单程耗时 $w$ 节。

输出格式

输出一行两个整数：备用路线的耗时，以及达到该耗时的走法种数对 $998244353$ 取模的余数。若 $1$ 号港与 $n$ 号港不连通，输出 -1 -1。

数据范围

• 特殊性质 A：所有航线的耗时节数都相同。
• 对于全部数据，$2 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$，$1 \le u, v \le n$，$u \ne v$，$1 \le w \le 10^4$。同一对港口之间可能有多条航线，不保证航线网连通。

样例

样例 1

输入：

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

输出：

4 1

解释：主用路线是 $1 \to 2 \to 4$，耗时 $1 + 2 = 3$。候选走法里，$1 \to 3 \to 4$ 耗时 $1 + 3 = 4$，比主用路线慢且慢得最少。再看看别的走法，比如 $1 \to 2 \to 1 \to 2 \to 4$，耗时 $1 + 1 + 1 + 2 = 5$，已经更慢了。耗时为 $4$ 的走法只有 $1 \to 3 \to 4$ 这一种，所以答案是 $4$ 和 $1$。

样例 2

输入：

3 3
1 2 2
2 3 2
1 3 9

输出：

8 2

解释：主用路线是 $1 \to 2 \to 3$，耗时 $4$。直航 $1 \to 3$ 耗时 $9$，看起来是备选，但有两种走法耗时都是 $8$，比 $9$ 更小：一种是 $1 \to 2 \to 1 \to 2 \to 3$，在 $1$、$2$ 之间折返一次，耗时 $2 + 2 + 2 + 2 = 8$；另一种是 $1 \to 2 \to 3 \to 2 \to 3$，在 $2$、$3$ 之间折返一次，耗时同样是 $8$。耗时为 $8$ 的走法恰有这两种，所以答案是 $8$ 和 $2$。

样例 3

输入：

3 1
1 2 1

输出：

-1 -1

解释：唯一的航线只连接 $1$ 号港和 $2$ 号港，$3$ 号港一条航线都没接上，从 $1$ 号港到不了 $3$ 号港，按格式输出两个 $-1$。