暂无测试数据。

题目背景

蒜头君得意洋洋的望着染色问题专题说：“小意思，我学会了～”

花椰妹感觉蒜头君太自满了，她转发给蒜头君一道题目，准备为难一下蒜头君。

题目描述

在一张 $n$ 个结点的 无向完全图 G 中，每条边有一种颜色（红色、绿色、蓝色），图中大部分边的颜色为绿色，部分边的颜色为红色或蓝色。

在 $G$ 中存在很多三角形（图中的顶点为三角形的顶点，图中的边为三角形的边），三角形共分为三种：

• 花色三角形：三条边的颜色均不同，价值为 $3$；
• 纯色三角形：三条边的颜色均相同，价值为 $-6$；
• 其他三角形：三条边只有两种颜色，价值为 $0$。

蒜头君需要求解出在 无向完全图 G 中，他可以获得的价值总和是多少。

输入格式

第一行以空格隔开输入两个正整数 $n,m$，分别表示 无向完全图 G 中顶点的个数、红色或蓝色边的个数；

接下来 $m$ 行，每行输入三个正整数 $u, v, c$，表示一条无向边 $(u,v)$ 的颜色为 $c$，若：

• $c = 1$，该边为红色；
• $c = 2$，该边为蓝色；

剩余边的颜色均为绿色。

输出格式

输出一个整数，无向完全图 G 中，蒜头君可以获得的价值总和。

数据范围

• 对于 $20\%$ 的数据，$1\leq n \leq 500, 1\leq m \leq \frac{n(n - 1)}{2}$；
• 对于 $40\%$ 的数据，$1\leq n \leq 2000, 1\leq m \leq \frac{n(n - 1)}{2}$；
• 对于 $100\%$ 的数据，$1\leq n \leq 100000, 1\leq m \leq \min\left(\frac{n(n - 1)}{2}, 200000\right)$；

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