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

Subtask 0 为民间数据，Subtask 1 为官方数据。

小可可来到了 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$ 时有两条路径。其中从 $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$。