题目描述

小 Z 有一个包含 $n$ 个节点和 $m$ 条边的无向图 $G$。

现在，小 Z 和小 Y 轮流将图中的一个点进行染色。小 Z 先手，小 Z 每次将一个节点染成黑色、小 Y 每次将一个节点染成白色，直至所有节点都被染色。

我们认为一条边是黑色的，当且仅当其两侧的点都是黑色的。 我们认为一条边是白色的，当且仅当其两侧的点都是白色的。

游戏得分定义为所有黑色边的边权之和减去所有白色边的边权之和（两侧颜色不同的边对得分没有贡献）。

小 Z 希望最大化游戏得分，而小 Y 希望最小化游戏得分。假设两个人都是绝顶聪明的人，请问最终的游戏得分是多少。

输入格式

第一行包含 $2$ 个正整数 $n, m$。

之后 $m$ 行，每行包含 $3$ 个正整数 $u_i, v_i, w_i$，表示一条 $(u_i, v_i)$ 间边权为 $w_i$ 的无向边，可能会有重边和自环。

输出格式

输出一行一个整数，表示最终答案。

样例

输入数据 1

3 3
1 2 1
2 3 2
1 3 4

输出数据 1

2

输入数据 2

10 12
1 3 2
3 5 3
1 4 5
2 5 6
2 6 7
2 7 8
2 8 9
1 9 10
9 10 7
1 3 5
2 2 10
4 4 3

输出数据 2

18

输入数据 3

16 19
1 3 2
2 3 4
1 4 5
2 5 6
2 6 7
2 7 8
2 8 9
1 9 10
8 2 7
1 3 5
1 4 3
4 4 3
10 7 2
11 8 12
12 4 152
13 2 1
14 4 123
15 12 4
16 1 2

输出数据 3

110

说明/提示

样例 1 解释

两人绝顶聪明的情况下，小 Z 会先染色 $3$ 号点、小 Y 再染色 $1$ 号点、小 Z 再染色 $2$ 号点，最终 $(2,3)$ 为黑边，答案为 $2$。

数据范围

对于 $40\%$ 的数据，$1 \le n \le 3$。

对于 $80\%$ 的数据，$1 \le n \le 16$。

对于 $100\%$ 的数据，$1 \le n, m \le 10^5$，$1 \le w_i \le 10^5$。