第一行两个整数 $n,m$ 表示点数与边数。点从 $1\sim n$ 编号。

接下来 $m$ 行每行三个整数 $a,b,c$ 表示一条连接 $(a,b)$ 的边权为 $c$ 的无向边。

边权以十进制形式给出。

仅一行一个整数表示答案。

样例输入

5 7
3 2 7400
4 1 1618
4 2 9110
4 3 4264
5 1 537
5 2 4240
5 3 655

样例输出

262221

$30\%$ 的数据（共六个点）：$n=5,6,7,8,9,10$
$50\%$ 的数据：$n\le 30$
$70\%$ 的数据：$n\le 40$
$100\%$ 的数据：n≤100,m≤n(n−1)2,0≤c≤104 n \le 100, m \le \frac{n(n-1)}{2}, 0 \leq c \leq 10 ^ 4 n≤100,m≤​2​​n(n−1)​​,0≤c≤10​4​​，保证无重边无自环。