各位观众，各位观众，您现在收看的是第 666 届跳蚤奥运会的比赛现场。在刚刚的五子棋比赛中，天才跳高小将“最强跳蚤”靠着“最强跳蚤跳跳跳”和经验丰富的伏特跳蚤国王大战了三天三夜，最后战成 $233:233$ 平。考虑到迟迟不能决出胜者，比赛组委会决定临时更换比赛项目，而被选中的则是在跳蚤大陆流行已久的运动项目——环城马拉松。

首先我来介绍一下比赛场地，微分方城有 $n$ 个路口，编号为 $1, \dots, n$。共有 $m$ 对路口间有无向道路相连，其中第 $i$ 对为 $u_i$ 号路口与 $v_i$ 号路口，且他们之间有 $t_i$ 条不同的无向道路。微分方城内任意两个路口都可以通过道路直接或间接到达，但由于微分方城的财政问题，有道路相连的路口对数 $m$ 不会超过 $n$。

现在，最强跳蚤和跳蚤国王的马拉松需要绕微分方城一周，即从某个起始点出发经过若干道路，再回到起始点。并且组委会规定，每条道路必须经过恰好一次。

那么问题来了，请观众朋友们数一数，一共有多少种环城马拉松的路线？最早给出答案的观众可以获得大火车一列哦。

路线可以认为是一个从某个点出发，由经过的道路编号和方向组成的序列。两条路线被认为是相同的当且仅当两序列相同，或更换起始边后两序列相同。请求出本质不同的路线的条数。

输入格式

第一行两个正整数 $n,m$，意义如前所述。

接下来 $m$ 行，每行三个正整数 $u_i,v_i,t_i$，表示 $u_i$ 到 $v_i$ 有 $t_i$ 条不同的无向道路。保证 $1 \le v_1, u_i \le n$，保证 $v_i \ne u_i$，且一对路口不会被重复描述。

输出格式

输出一行一个整数表示答案对 $998244353$（$7 \times 17 \times 2^{23} + 1$，一个质数） 取模后的结果。

样例一

input

2 1
1 2 4

output

12

explanation

把 $4$ 条道路编号为 $1, 2, 3, 4$，则路线有：（简洁起见没有标出方向，下面的路线均以 $1$ 号城市为起点） \begin{equation} (1,2,3,4);(1,2,4,3);(1,3,2,4);(1,3,4,2);(1,4,2,3);(1,4,3,2);(2,1,3,4);(2,1,4,3);(3,1,2,4);(3,1,4,2);(4,1,2,3);(4,1,3,2) \end{equation} 其余路线与上述 $12$ 种路线等价。

样例二

input

3 2
1 2 4
2 3 2

output

48

样例三

input

3 3
1 2 3
2 3 3
3 1 3

output

3168

样例四

input

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

output

474218496

样例五

见样例数据下载

限制与约定

在所有数据中，满足 $1 \leq n-1 \leq m \leq n \leq 1000$ 且 $1 \leq t_i \leq 10^4$。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载