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

P12250 [科大国创杯初中组 2025] 旅行

题目背景

民间数据，仅供参考。

题目描述

小可可来到了 P 国旅行。

P 国共有 $n$ 个城市和 $m$ 条有向道路，其中第 $i$ 条道路为从城市 $u_i$ 到城市 $v_i$，长度为 $w_i$。保证 $u_i < v_i$。

对于一次游览，假设小可可依次经过了城市 $x_1, x_2, \ldots, x_k$，其中从 $x_i$ 到 $x_{i+1}$ 经过的路径长度为 $y_i$。记 $s_i$ 表示 $y_1, y_2, \ldots, y_i$ 的按位或值。那么小可可认为这次游览就是从 $x_1$ 走到 $x_k$，疲劳度就是 $\operatorname{mex}(s_1, s_2, \ldots, s_{k-1})$。

其中 $\operatorname{mex}(a_1, a_2, \ldots, a_n)$ 表示最小的没有出现在 $a_1, a_2, \ldots, a_n$ 中的自然数。例如 $\operatorname{mex}(0, 2, 3) = 1$，$\operatorname{mex}(1, 4) = 0$，$\operatorname{mex}(0, 1, 2, 3, 4) = 5$。

小可可认为两座城市 $s, t$ 之间的距离为他从 $s$ 走到 $t$ 所有可能的游览方案中疲劳度的最大值，记作 $d(s, t)$。如果不能从 $s$ 走到 $t$，那么 $d(s, t) = -1$。规定 $d(s, s) = 0$。现在他想要知道任意两座城市之间的距离之和，即 $\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} d(i, j)$。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行三个整数，代表 $u_i, v_i, w_i$。

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

3 3
1 2 0
1 3 2
2 3 1

输出 #1

0

说明/提示

样例 1 解释

当从 $1$ 走到 $3$ 时有两条路径。其中从 $1$ 直接到 $3$ 疲劳度为 $\operatorname{mex}(2) = 0$。从 $1$ 到 $2$ 再到 $3$ 疲劳度为 $\operatorname{mex}(0, 1) = 2$。所以 $1$ 到 $3$ 的距离为 $2$。

以此类推，有 $d(1, 1) = d(2, 2) = d(3, 3) = 0$。$d(2, 1) = d(3, 1) = d(3, 2) = -1$。$d(1, 2) = 1$，$d(1, 3) = 2$，$d(2, 3) = 0$。总和为 0。

数据规模与约定

• 对于 $10\%$ 的数据，保证 $n \leq 3$，$m \leq 5$。
• 对于 $25\%$ 的数据，保证 $n \leq 20$，$m \leq 40$。
• 对于 $45\%$ 的数据，保证 $n \leq 300$，$m \leq 500$。
• 对于 $60\%$ 的数据，保证 $n \leq 3000$，$m \leq 5000$。
• 对于另外 $10\%$ 的数据，保证 $w_i \geq 1$。
• 对于另外 $10\%$ 的数据，保证 $m = n - 1$，$u_i = i$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 3 \times 10^4$，$1 \leq m \leq 2 \times 10^5$，$1 \leq u_i < v_i \leq n$，$0 \leq w_i \leq 10^9$。