Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh và ~m~ cạnh không chứa khuyên, mỗi cạnh có dạng ~(u,v,c)~, tức là cạnh nối hai đỉnh ~u~ và ~v~ có trọng số ~c~. Lưu ý, không tồn tại quá 5 cạnh có cùng trọng số là ~c~.

Hãy đếm số cây khung nhỏ nhất của đồ thị này. Nói cách khác, đếm số cách giữ lại ít cạnh nhất của đồ thị sao cho đồ thị vẫn liên thông và tổng trọng số các cạnh giữ lại là nhỏ nhất.

Do kết quả có thể rất lớn, hãy in ra đáp số theo modulo ~998244353~.

Input

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~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^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.
• Dữ liệu đảm bảo đồ thị liên thông.

Output

• Gồm một số nguyên duy nhất là số cây khung nhỏ nhất của đồ thị modulo ~998244353~.

Scoring

Example

Sample Input 1

3 3
1 2 1
2 3 1
3 1 1

Sample Output 1

3

Sample Input 2

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

Sample Output 2

2

Sample Input 3

4 9
1 2 1
1 2 1
2 3 2
2 3 2
2 3 2
3 4 3
3 4 3
3 4 3
3 4 3

Sample Output 3

24