Hôm nay Rikka nhận được một đồ thị vô hướng $G$ với $n$ đỉnh và $m$ cạnh. Các đỉnh được đánh số bằng các số nguyên từ $1$ đến $n$. Cạnh thứ $i$ nối hai đỉnh $u_i$ và $v_i$, với trọng số là $w_i$.

Rikka thích các đồ thị Hamilton: những đồ thị có chu trình Hamilton. Do đó, Rikka xây dựng một đồ thị dựa trên $G$ chắc chắn là đồ thị Hamilton. Cô ấy thực hiện điều này bằng cách thêm $n$ cạnh phụ: cạnh thứ $i$ nối hai đỉnh $i$ và $(i \pmod n + 1)$, với trọng số là $10^9$.

Gọi $c(i, j)$ là giá trị của lát cắt tối thiểu giữa đỉnh thứ $i$ và đỉnh thứ $j$. Rikka muốn bạn tính: $$\sum_{i=1}^{n} \sum_{j=i+1}^{n} c(i, j)$$

Với một đồ thị $G_0 = \langle V, E \rangle$, một tập hợp các cạnh $C \subseteq E$ là một lát cắt giữa hai đỉnh $i$ và $j$ khi và chỉ khi trong đồ thị $G_1 = \langle V, E \setminus C \rangle$, hai đỉnh $i$ và $j$ không được kết nối (trực tiếp hoặc gián tiếp). Lát cắt tối thiểu giữa $i$ và $j$ là lát cắt có tổng trọng số các cạnh nhỏ nhất. Giá trị $c(i, j)$ của lát cắt tối thiểu chính là tổng trọng số nhỏ nhất đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($3 \le n \le 20\,000$, $0 \le m \le 20\,000$).

Tiếp theo là $m$ dòng. Mỗi dòng chứa ba số nguyên $u_i$, $v_i$ và $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$ và $1 \le w_i \le 10\,000$).

Lưu ý rằng đồ thị không có khuyên (self-loop), nhưng có thể chứa đa cạnh.

Dữ liệu ra

In ra một dòng duy nhất chứa một số nguyên là kết quả theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

4 2
1 3 2
2 4 2

Dữ liệu ra 1

21067776