该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】

小 C 喜欢旅行。

小 C 给了你一棵包含 $n$ 个节点的树，每一条边 $(u_i,v_i)$ 拥有一个非负权值 $w_i$。

定义 $d(u,v)$：从 $u$ 到 $v$ 的唯一路径上边权的最大值。

求最大的 $\sum_{i=2}^{n} n^{d(p_{i-1},p_i)}$，满足 $p_1,p_2,\cdots,p_n$ 是 $1,2,\cdots,n$ 的排列。

【输入格式】

第一行包含一个整数 $n\ (2 \le n \le 100000)$，表示树的节点数量。

对于接下来的 $n-1$ 行，每行包含三个整数 $u_i,v_i,w_i$ 表示第 $i$ 条边连接 $u_i$ 与 $v_i$，权值为 $w_i$。

【输出格式】

输出一个数，表示最优解。由于答案过大，请输出答案对 $998244353$ 取模后的结果。

【测试样例】

5
1 2 0
2 3 0
3 4 0
4 5 1

12

9
2 1 1
3 1 1
1 4 0
5 1 2
6 4 1
2 7 2
8 4 2
8 9 3

1944

【数据范围与约定】

对于 $20\%$ 的测试点，满足 $n \le 9$。

对于 $40\%$ 的测试点，满足 $n \le 20$。

对于 $60\%$ 的测试点，满足 $n \le 1000$。

另有 $20\%$ 的测试点，满足 $w_i \le 1$。

对于全部测试点，满足 $2 \le n \le 100000, 1 \le u_i, v_i \le n, 0 \le w_i \le 30$。