题目描述

给定一张 $n$ 个点 $m$ 条边的有向图。第 $i$ 条边连接结点 $u_i$ 和 $v_i$。你初始在 $1$ 号结点，每个时刻，你可以在以下两种操作中选择一种：

$\bullet$ 移动：如果存在一条 $u\rightarrow v$ 的边，可以花费 $1$ 的时间，从结点 $u$ 移动到结点 $v$。

$\bullet$ 翻转：如果这是第 $k$ 次翻转操作，可以花费 $2^{k-1}$ 的时间将图上所有边反向。

请你求出从 $1$ 号点到 $n$ 号点需要花费的最少时间，对 $998244353$ 取模，如果无法到达输出 $-1$。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行每行三个整数 $u_i,v_i$，表示一条边。

输出格式

一行一个整数表示答案。

4 4
1 2
2 3
3 4
4 1

2

4 3
2 1
2 3
4 3

10

数据范围

$$\begin{aligned} & \bullet \ 1 \le n, m \le 2\times 10^5\\ & \bullet \ 1 \le u_i,v_i \le n\\ & \bullet 不含重边和自环 \end{aligned}$$