在神秘的大清，有更多的ddl，就会有更多咕咕咕的方法。

准确的说，ddl是一棵大小为 $n$ 的树，第一个节点是网络科学，第二个节点是博弈论...

Lyra 的暑期计划（除了陪 Evan 之外）是一个每个元素在 $[1,n]$ 的序列，她计划完成一个长度为偶数的子区间的ddl，并且咕咕咕掉剩下的。

她会给区间内的ddl两两配对，两个ddl如果很接近，那么她就只需要把第一个ddl要交的作业稍作修改，在网络学堂上上传到第二个ddl。

Lyra 很聪明，所以她总是能巧妙的把区间内的ddl两两匹配使得匹配的ddl之间在树上的距离之和（唯一简单路上的边权和）最小。每个长度为偶数的区间的完成时间定义为最小配对方法中每对匹配点间距离的总和。

作为 Lyra 的朋友，你要帮她求序列每个长度为偶数的区间的ddl的完成时间之和。

输入格式

第一行两个整数 $n, m$ 表示树的大小和序列的长度。

接下来 $n-1$ 行每行三个整数 $u, v, w$ 表示一条连接 $u, v$ 长度为 $w$ 的树边。

接下来一行 $m$ 个整数表示序列。

注意：本题输入可能很大，建议采用较为快速的读入方式。

输出格式

一行一个整数表示答案，由于答案可能很大，输出其对 $998244353$ 取模的结果。

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

11

一共只有 $4$ 个区间需要计算，点集分别为 $\{2, 3\}, \{3, 1\}, \{1, 4\}, \{2, 3, 1, 4\}$， 最小完成时间分别为 $2, 3, 4, 2$，于是总和为 $11$。

7 7
1 2 5
1 3 4
2 4 3
2 5 2
3 6 1
3 7 2
1 5 3 6 7 5 1

102

样例三

见样例数据下载。

限制与约定

本题采用捆绑测试，只有通过一个子任务的全部测试点才可以得到子任务的得分。

对于全部数据 $1 \leq n, m \leq 10^5; 1 \leq w \leq 10^9.$

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载