题目描述

小可可来到了 $P$ 国旅行。

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

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

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

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

输入格式

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

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

输出格式

一行一个整数表示答案。

样例 1

3 3
1 2 0
1 3 2
2 3 1

0

样例 1 解释

当从 $1$ 走到 $3$ 时有两条路径。其中从 $1$ 直接到 $3$ 疲劳度为 $mex(2) = 0$。从 $1$ 到 $2$ 再到 $3$ 疲劳度为 $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 ≤ 3$, $m ≤ 5$。

对于 $25\%$ 的数据，保证 $n ≤ 20, m ≤ 40$。

对于 $45\%$ 的数据，保证 $n ≤ 300$, $m ≤ 500$。

对于 $60\%$ 的数据，保证 $n ≤ 3000$, $m ≤ 5000$。

对于另外 $10\%$ 的数据，保证 $w_i ≥ 1$。

对于另外 $10\%$ 的数据，保证 $m = n − 1$，$u_i = i$。

对于 $100\%$ 的数据，保证 $1 ≤ n ≤ 3 × 10^4$ , $1 ≤ m ≤ 2 × 10^5$ , $1 ≤ u_i < v_i ≤ n$ , $0 ≤ w_i ≤ 10^9$。

ex_trip1.in  ex_trip1.ans

ex_trip2.in  ex_trip2.ans

ex_trip3.in  ex_trip3.ans

ex_trip4.in  ex_trip4.ans

ex_trip5.in  ex_trip5.ans