You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小可可来到了 P 国旅行。

P 国共有 n 个城市和 m 条有向道路，其中第 i 条道路为从城市 ui 到城市 vi ，长度 为 wi 。保证 ui < vi**。**

对于一次游览，假设小可可依次经过了城市 x1 , x2, ..., xk ，其中从 xi 到 xi+1 经过的 路径长度为 yi。记 si 表示 y1 , y2 , ..., yi 的按位或值。那么小可可认为这次游览就是从 x1 走到 xk ，疲劳度就是 mex (s1 , s2, ..., sk- 1 )。

其中 mex (a1 , a2, ..., an ) 表示最小的没有出现在 a1 , a2 , ..., an 中的自然数。例如 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。现 在他想要知道任意两座城市之间的距离之和，即

输入格式

第一行两个整数 n, m。

接下来 m 行，每行三个整数，代表 ui , vi , wi。

输出格式

一行一个整数表示答案。

样例****1​输入

3 3
1 2 0
1 3 2
2 3 1

样例****1​输出

0

样例****2/3/4/5​输入

详见选手文件夹下的 trip/trip*.in 文件。

样例****2/3/4/5​输出

详见选手文件夹下的 trip/trip*.ans 文件。

样例****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% 的数据，保证 wi ≥ 1。

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

对于 100% 的数据，保证 1 ≤ n ≤ 3 × 10^4 , 1 ≤ m ≤ 2 × 10^5 , 1 ≤ ui < vi ≤ n, 0 ≤ wi ≤ 10^9。