// by deepseek #include <bits/stdc++.h> using namespace std; const int MOD = 998244353; const int MAXN = 200005; const int MAXM = 500005; // 快速幂 long long pow_mod(long long a, long long b) { long long res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } // 预处理阶乘和逆元 long long fact[MAXN * 2], inv_fact[MAXN * 2]; void precompute_factorials(int n) { fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = fact[i - 1] * i % MOD; } inv_fact[n] = pow_mod(fact[n], MOD - 2); for (int i = n - 1; i >= 0; i--) { inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD; } } // 组合数计算 long long nCr(int n, int r) { if (r < 0 || r > n) return 0; return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD; } // 计算从0开始n步内从未访问d的路径数 long long never_visit(int n, int d) { if (d == 0) return 0; // 起点总是被访问 long long total = 0; int abs_d = abs(d); // 使用反射原理计算从未访问d的路径数 for (int j = -n; j < abs_d; j += 2) { if ((n + j) % 2 != 0) continue; int k1 = (n + j) / 2; int k2 = (n + j + 2 * abs_d) / 2; if (k1 >= 0 && k1 <= n) { total = (total + nCr(n, k1)) % MOD; } if (k2 >= 0 && k2 <= n) { total = (total - nCr(n, k2) + MOD) % MOD; } } return total; } // 计算访问d的概率 long long visit_prob(int n, int d) { if (d == 0) return 1; // 起点总是被访问 long long never = never_visit(n, abs(d)); long long total_paths = pow_mod(2, n); long long visit_paths = (total_paths - never + MOD) % MOD; return visit_paths * pow_mod(total_paths, MOD - 2) % MOD; } // 计算支付概率 long long payment_prob(int n, int s, int t) { if (s == t) { return visit_prob(n, s); } else { // 简化处理：假设访问s和t是独立事件 // 实际应该计算联合概率，这里使用近似 long long prob_s = visit_prob(n, s); long long prob_t = visit_prob(n, t); return prob_s * prob_t % MOD; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; precompute_factorials(2 * n); long long ans = 0; for (int i = 0; i < m; i++) { int s, t, v; cin >> s >> t >> v; long long prob = payment_prob(n, s, t); ans = (ans + v * prob % MOD) % MOD; } cout << ans << endl; return 0; }