Kaguya wants to design a graph theory problem.

Given an undirected graph $G$ with $n$ vertices and $m$ edges without self-loops, where the $i$-th edge connects $(u_i, v_i)$ with weight $w_i$ ($1 \leq w_i \leq 10^4$).

Based on $G$, Kaguya constructs a new graph $G'$, where $G'$ is formed by adding $n$ edges to $G$. The $i$-th added edge connects $i$ and $i \text{ mod } n + 1$ with a weight of $10^9$.

Let $f(u, v)$ be the size of the minimum cut between $u$ and $v$ in $G'$. Kaguya wants you to calculate $\sum_{i=1}^n \sum_{j=i+1}^{n} f(i, j)$.

An edge set $E$ is a cut between $u$ and $v$ if and only if $u$ cannot reach $v$ after removing the edges in $E$. The size of a cut is defined as the sum of the weights of all edges in the cut, and the minimum cut between $u$ and $v$ is the cut with the minimum size among all such cuts.

Input

The first line contains two integers $n, m$ ($1 \leq n \leq 7000, 1 \leq m \leq 10^5$).

The next $m$ lines each contain three integers $u_i, v_i, w_i$ ($1 \leq u_i \neq v_i \leq n, 1 \leq w_i \leq 10^4$), describing an edge in $G$.

Output

Output a single integer representing the answer. Since the answer may be very large, output it modulo $998244353$.

Subtasks

Subtask 1 (19 points): $n \leq 80, m \leq 200$.

Subtask 2 (23 points): $n \leq 300, m \leq 1000$.

Subtask 3 (26 points): $n \leq 1000$.

Subtask 4 (32 points): No additional constraints.

Examples

Input 1

4 2
1 3 2
2 4 2

Output 1

21067776