Đếm cây khung

Với một đồ thị vô hướng liên thông, cây khung là một cách giữ lại một số ít cạnh nhất của đồ thị sao cho đồ thị vẫn liên thông. Nếu các cạnh của đồ thị gốc có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh được giữ lại là nhỏ nhất.

Cho một đồ thị vô hướng liên thông có trọng số gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\), các cạnh được gán trọng số là các số nguyên dương sao cho, với mọi số nguyên dương \(c\), không tồn tại quá \(5\) cạnh có trọng số \(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 được giữ lại là nhỏ nhất.

Do kết quả có thể rất lớn, bạn chỉ cần đưa ra đáp số theo modulo \(998244353\).

Input

Dòng đầu tiên chứa số nguyên \(θ\) \((1 ≤ θ ≤ 5)\) là số thứ tự cùa subtask chứa test này.

Dòng thứ hai chứa hai số nguyên \(n\) và \(m\) \((1 ≤ n ≤ 2·10^5, 1 ≤ m ≤ 3·10^5)\), lần lượt là số đỉnh và số cạnh của đồ thị.

\(m\) dòng cuối cùng, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(c\) \((1 ≤ u, v ≤ n, 1 ≤ c ≤ m)\) cho biết trên đồ thị có một cạnh nối hai đỉnh \(u\) và \(v\) với trọng số \(c\).

Dữ liệu vào đảm bảo đồ thị liên thông, và với mọi số nguyên dương \(c\), không có quá \(5\) cạnh của đồ thị có trọng số này.

Output

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

Example

1
3 3
1 2 1
2 3 1
3 1 1

3

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

2

5
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

24

Scoring

Subtask \(1\) (\(14\) điểm): \(m ≤ 7\)

Subtask \(2\) (\(18\) điểm): \(m ≤ 25\)

Subtask \(3\) (\(18\) điểm): Tồn tại tối đa một số nguyên \(c\) sao cho đồ thị có nhiều hơn một cạnh với trọng số \(c\).

Subtask \(4\) (\(20\) điểm): \(m = n\)

Subtask \(5\) (\(30\) điểm): Không có ràng buộc gì thêm.