牛奶

题号：NC217860
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Oshama Scramble!

给定一张 $n$ 个结点 $m$ 条边的无向连通图，点以 $1,2,\dots,n$ 编号，边有长度。

你需要把点集 $V$ 划分为若干个有标号集合 $S_1,S_2,\dots,S_k$ 。
具体地，需要满足：

对于 $1 \le i \le k$ ， $S_i \ne \varnothing$ 。
对于 $1 \le i < j \le k$ ， $S_i \cap S_j = \varnothing$ 。
$S_1 \cup S_2 \cup \cdots \cup S_k = V$ 。

对于一种划分方案的一个集合 $S_i$ ，定义其「牛奶结点」为 $S_i$ 内满足在原图中到 $S_i$ 内其它结点的最短距离之和最小的结点。可能存在多个牛奶结点。
这个集合 $S_i$ 的权值定义为牛奶结点在原图中到 $S_i$ 内所有结点的最短距离之和加一。
一个划分方案的权值为所有集合的权值的乘积。
求所有划分方案的权值之和。
对 $998244353$ 取模。

输入描述:

第一行，两个正整数 。
以下  行，每行三个正整数 ，表示一条连接 ，长度为  的边。

输出描述:

一行一个非负整数，表示答案。

示例1

输入

复制

输出

复制

备注:

，，，。