오늘 Rikka는 $n$개의 정점과 $m$개의 간선으로 이루어진 무방향 그래프 $G$를 받았습니다. 정점은 $1$부터 $n$까지의 정수로 번호가 매겨져 있습니다. $i$번째 간선은 정점 $u_i$와 $v_i$를 연결하며, 가중치는 $w_i$입니다.

Rikka는 해밀턴 경로가 존재하는 그래프인 해밀턴 그래프를 좋아합니다. 따라서 Rikka는 $G$를 기반으로 반드시 해밀턴 그래프가 되는 새로운 그래프를 구성합니다. 그녀는 $n$개의 추가 간선을 삽입하여 이를 수행하는데, $i$번째 추가 간선은 정점 $i$와 $(i \pmod n + 1)$을 연결하며 가중치는 $10^9$입니다.

$c(i, j)$를 $i$번째 정점과 $j$번째 정점 사이의 최소 컷(minimal cut)의 값이라고 합시다. Rikka는 여러분이 다음 식을 계산하기를 원합니다.

$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} c(i, j)$$

그래프 $G_0 = \langle V, E \rangle$가 주어졌을 때, 간선의 집합 $C \subseteq E$가 정점 $i$와 $j$ 사이의 컷(cut)이라는 것은 그래프 $G_1 = \langle V, E \setminus C \rangle$에서 정점 $i$와 $j$가 (간접적으로든 직접적으로든) 연결되어 있지 않을 때를 의미합니다. $i$와 $j$ 사이의 최소 컷은 간선 가중치의 합이 최소인 컷입니다. 최소 컷의 값 $c(i, j)$는 이 최소 합 그 자체입니다.

입력

첫 번째 줄에는 두 정수 $n$과 $m$ ($3 \le n \le 20\,000$, $0 \le m \le 20\,000$)이 주어집니다.

그다음 $m$개의 줄이 이어집니다. 각 줄에는 세 정수 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$, $1 \le w_i \le 10\,000$)가 주어집니다.

그래프에는 자기 루프(self-loop)가 없지만, 다중 간선이 포함될 수 있음에 유의하십시오.

출력

한 줄에 하나의 정수로, 답을 $998\,244\,353$으로 나눈 나머지를 출력하십시오.

예제

입력 1

4 2
1 3 2
2 4 2

출력 1

21067776