LaLa 的妹妹 LiLi 正在帮助 LaLa 施展召唤精灵的魔法。

在 LaLa 睡觉时，LiLi 已经构建了一个待召唤精灵的原型。该精灵由 $N$ 个魔法关节组成，这些关节允许连接到它们上面的任何魔法棒绕其自由转动；此外还有 $M$ 根各种颜色的魔法棒，每根魔法棒连接两个魔法关节，其长度可以在召唤前（但不能在召唤后）调整为任何非负实数。

在召唤精灵时，LaLa 的标准远高于 LiLi。当然，LaLa 对 LiLi 的工作一点也不满意。LaLa 想要通过去掉一些魔法棒来美化这个原型，使得：

1. 精灵是“美观”的，这意味着不存在两根颜色相同的魔法棒，并且
2. 精灵尽可能易于控制，这意味着在通过消除一些魔法棒所能获得的所有美观精灵中，该精灵的自由度必须最小。注意，最小值总是存在的，因为她总是可以消除所有魔法棒来创造一个美观的精灵。关于自由度的确切定义，请参阅下文的说明。

编写一个程序，计算 LaLa 美化后的精灵的自由度。

输入格式

输入描述了 LiLi 制作的精灵原型，格式如下：

$N$ $M$ $u_0$ $v_0$ $c_0$ $u_1$ $v_1$ $c_1$ $\vdots$ $u_{M-1}$ $v_{M-1}$ $c_{M-1}$

其中 $N$ 是魔法关节的数量，编号从 $0$ 到 $N-1$，$M$ 是魔法棒的数量，对于每个整数 $0 \le i < M$，第 $i$ 根魔法棒的颜色为 $c_i$，连接魔法关节 $u_i$ 和 $v_i$。

输入满足以下约束：

• 所有输入数字均为整数。
• $2 \le N \le 200$
• $0 \le M \le 1\,000$
• 对于所有整数 $0 \le i < M$，满足 $0 \le u_i < v_i < N$ 且 $0 \le c_i < M$

注意：可能存在多根魔法棒连接同一对魔法关节。

输出格式

输出应为一个单一整数，等于 LaLa 美化后的精灵的自由度。

样例

样例输入 1

3 3
0 1 0
0 2 0
1 2 0

样例输出 1

5

样例输入 2

3 3
0 1 0
0 2 1
1 2 2

样例输出 2

3

样例输入 3

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

样例输出 3

4

样例输入 4

5 4
0 1 0
1 2 1
2 3 2
3 4 3

样例输出 4

6

说明

直观地说，自由度是嵌入在平面上的精灵保持边长不变的运动轴的数量。

更正式地，设 $E$ 为精灵所有魔法关节的平面坐标分配（我们称之为嵌入）。注意，这样的嵌入可以通过连接所有坐标被识别为 $\mathbb{R}^{2N}$ 中的一个元素，其中 $N$ 是魔法关节的数量。

设 $C(E)$ 为从 $E$ 出发，在保持边长不变的情况下，作为 $\mathbb{R}^{2N}$ 中的元素可以连续到达的所有嵌入的集合。即对于 $C(E)$ 中的每个元素 $E'$ 以及精灵中连接魔法关节 $u$ 和 $v$ 的每根魔法棒，在 $E$ 和 $E'$ 中 $u$ 与 $v$ 之间的欧几里得距离必须相同。

$E$ 的自由度是最小的非负整数 $k$，使得存在一个连续双射映射 $F : D \to C(E)$，其中 $D$ 是 $\mathbb{R}^k$ 的一个连通子集。

精灵的自由度是所有此类嵌入 $E$ 中的最大自由度。

以下按顺序展示了 LaLa 美化后的精灵，以及每个样例测试中一个最优嵌入和对应的映射 $F$。

1. $k = 5, D = \mathbb{R}^2 \times [0, 2\pi) \times \mathbb{R}^2$ $F : (x_0, x_1, x_2, x_3, x_4) \mapsto \langle(x_0, x_1), (x_0, x_1) + (\cos x_2, \sin x_2), (x_3, x_4)\rangle$ 下图展示了与每个变量相关的 5 个自由度。

1. $k = 3, D = \mathbb{R}^2 \times [0, 2\pi)$ $F : (x_0, x_1, x_2) \mapsto \langle(x_0, x_1), (x_0, x_1) + (\cos x_2, \sin x_2), (x_0, x_1) + (\cos (\frac{\pi}{3} + x_2), \sin (\frac{\pi}{3} + x_2))\rangle$ 下图展示了与每个变量相关的 3 个自由度。

1. $k = 4, D = \mathbb{R}^2 \times (((0, 2] \times [0, 2\pi)) \cup (\{0\} \times [0, \pi)))$ $F : (x_0, x_1, x_2, x_3) \mapsto \langle P_0, P_0 + \frac{x_2}{2} P_1 + \sqrt{1 - \frac{x_2^2}{4}} P_2, P_0 + x_2 P_1, P_0 + \frac{x_2}{2} P_1 - \sqrt{1 - \frac{x_2^2}{4}} P_2 \rangle$ 其中 $P_0 = (x_0, x_1), P_1 = (\cos x_3, \sin x_3)$ 且 $P_2 = (\sin x_3, -\cos x_3)$。 左图展示了与每个变量相关的 4 个自由度。注意与变量 $x_2$ 相关的运动是非刚性的。右图详细展示了与 $x_2$ 相关的运动。

1. $k = 6, D = \mathbb{R}^2 \times [0, 2\pi)^4$ $F : (x_0, x_1, x_2, x_3, x_4, x_5) \mapsto \langle P_0, P_1, P_2, P_3, P_4 \rangle$ 其中 $P_0 = (x_0, x_1)$ 且对于所有整数 $1 \le i \le 4$，$P_i = P_{i-1} + (\cos x_{i+1}, \sin x_{i+1})$。 下图展示了与每个变量相关的 6 个自由度。