小月的炼金术
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}在一个古老的炼金术矩阵中，有 n 个能量核心，编号为 1,2,\dots,n 。
\hspace{15pt}不同核心之间可以通过 m 条能量管道连接。管道分为三种类型：
\hspace{23pt}\bullet\,火元素管道：类型为 0，赋予网络热能。
\hspace{23pt}\bullet\,冰元素管道：类型为 1，赋予网络冷能。
\hspace{23pt}\bullet\,普通管道：类型为 2，仅仅起到连接作用，不产生热能或冷能。
\hspace{15pt}第 i 条管道连接核心 u_i 和 v_i，具有强度 w_i 和类型 t_i\in\{0,1,2\}（对应上述三种）。

\hspace{15pt}为了激活炼金矩阵，你需要选择 n-1 条管道构成一棵生成树，但这棵生成树必须满足“热力学平衡”：生成树中火元素管道的数量减去冰元素管道的数量，必须是 3 的倍数。换句话说，即：

{\rm cnt}_{\text{火元素管道}}-{\rm cnt}_{\text{冰元素管道}}\equiv 0 \pmod 3

\hspace{15pt}生成树的权值定义为所有选中管道强度 w_i 的乘积，请计算所有满足“热力学平衡”条件的生成树的权值之和。由于答案可能很大，请将答案对 998\,244\,353 取模后输出。

【名词解释】
\hspace{15pt}生成树：对于一张由 n 个顶点构成的图，任选其中 n-1 条边，使得所有顶点连通，这些边会组成一棵树，称为这张图的一棵生成树。

输入描述:

\hspace{15pt}第一行输入两个整数 n,m \left( 2\leq n\leq 100;\, n-1\leq m\leq 5 \times 10^3 \right)，表示能量核心数量、能量管道数量。
\hspace{15pt}此后 m 行，第 i 行输入四个整数 u_i,v_i,w_i,t_i \left( 1\leq u_i,v_i\leq n;\, u_i \neq v_i;\, 1\leq w_i < 998\,244\,353;\, t_i \in \{0,1,2\} \right)，表示第 i 条管道双向连接核心 u_i 和 v_i，具有强度 w_i 和类型 t_i。
\hspace{15pt}保证炼金术矩阵连通。不存在重边（任意两个核心之间最多只有一条管道，无论类型如何）、不存在自环。

输出描述:

\hspace{15pt}输出一个整数，表示所有满足“热力学平衡”条件的生成树的权值之和对 998\,244\,353 取模后的结果。
示例1

输入

复制 
3 3
1 2 1 0
2 3 1 1
1 3 1 0

输出

复制 
2
示例2

输入

复制 
5 6
5 1 7 1
2 5 6 0
3 5 1 0
4 5 3 2
3 1 4 1
2 4 2 2

输出

复制 
66