暂无测试数据。

刚刚上高中的洁洁在学习组合数学的过程中遇到一道麻烦的题目，她希望你能帮助她解决。给定一张无向完全图 $G$，其中大部分边被染成蓝色，但也有一些边被染成红色或者绿色。现在，洁洁需要给这张图的多样性进行打分。一张图的多样性取决于它的同色和异色三角形的个数。具体来说，$G$ 中每有一个三边颜色都互不同的三角形（异色三角形）可以得 $3$ 分，每有一个三边颜色都相同的三角形（同色三角形）则要被扣掉 $6$ 分，其它三角形不得分也不扣分。

现在，请你写一个程序来计算 $G$ 的多样性分数。

输入格式

第一行两个正整数 $n$ 和 $m$，其中 $n$ 表示 $G$ 中顶点的个数，$m$ 表示 $G$ 中红色或者绿色的边的条数。

接下来 $m$ 行每行包括三个整数 $a,b,c$，代表连接顶点 $a$ 和顶点 $b$ 的边颜色为红色 $(c=1)$ 或者绿色 $(c=2)$。

输出格式

一行，$G$ 的多样性得分。

数据范围与约定

对于 $20\%$ 的数据，$n \le 500,m \le \frac{n(n-1)}{2}$。

对于 $40\%$ 的数据，$n \le 2000,m \le \frac{n(n-1)}{2}$。

对于 $100\%$ 的数据，$n \le 100000, m \le min(\frac{n(n-1)}{2},200000)$。

样例解释 1

$(1, 2, 3)$ 能组成一个同色三角形，找不到异色三角形，得分为 $-6$。

样例解释 2

$(1, 2, 3)$ 能组成一个同色三角形，$(1,2,4),(1,3,4)$ 能组成两个异色三角形，得分为 $2*3-6=0$。

4 3
1 2 1
1 3 1
2 3 1

-6

4 4
1 2 1
1 3 1
2 3 1
1 4 2

0