染色

时间限制：1000ms

内存限制：512MB

问题描述

给定 $n$ 个节点 $m$ 条边的无向图 $G$。

Alice 和 Bob 轮流给图中的一个点进行染色，Alice 先手，Alice 每次把一个节点染成黑色，Bob 每次把一个节点染成白色，直至所有点都被染上颜色。

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

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

游戏得分为所有黑色边的边权之和减去白色边的边权之和。

Alice 希望最大化游戏得分,Bob 希望最小化游戏得分，假设两人绝顶聪明，请你输出最终的游戏得分。

输入格式

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

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

输出格式

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

样例输入1

3 3
1 2 1
2 3 2
1 3 4

样例输出1

2

样例解释

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

样例输入2

10 12
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
2 2 10
4 4 3

样例输出2

26

样例输入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
2 2 10
4 4 3
10 7 2
11 8 12
12 4 132
13 2 1
14 4 123
15 12 4
16 1 2

样例输出3

100

评测数据规模

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

对于 $80\%$ 的数据，$1 \leq n \leq16$​。

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