本题没有可用的提交语言。

题目描述

“在清晨的阳光中，晨星（Phosphor）在朝霞中闪耀。她是最明亮的那颗星。她的光芒悬挂在高空，有时在洁白的墙面上颤动，仿佛想向我们诉说这滚滚红尘中动人的故事。”现在我们听听她讲的一个故事：

“不久前（对她而言，即使人类眼中的千年也只是刹那）——我的光芒照到了一个叫 Remmarguts 的王子（真奇怪的语言），他是 UDF（United Delta of Freedom，自由三角洲联盟）王国中被公认最聪明、最善良的人。”

她继续说：

“那是一个异常寒冷的日子，雪花飘落着，其中一片落在一个大盒子上。雪花越变越大，最后化作一位白衣少女！她说：‘我是女神 Uohzgnah，我要告诉你邪恶之神 Ahriman 带来的灾难。我们唯一能阻止 Ahriman 重建恶魔世界的方法，就是解开她设置的谜题。我们已尽全力，却失败了。智慧的王子，我将这个机会交给你——’”

Ahriman 给了王子 $N$ 个橘子皮碎片（$4 \leq N \leq 269$），她将这些碎片连成了一个连通图。如题图所示。

此外，她用魔法在一些碎片之间系上了 $M$ 条彩绳（$N-1 \leq M \leq \frac{N(N-1)}{2}$），彩绳有三种颜色：

白色（peace）

浅绿色（nature）

浅蓝色（people）

王子获得了两个魔法道具：

可以识别绳子的颜色。

可以切断任何一条绳子。

王子的目标：

在保证任何 $K$（$2 \leq K \leq N$）个编号为 $1$ 到 $K$ 的碎片始终保持连通的前提下：

删除尽可能多的绳子

保留的彩绳中，使三种颜色中数量最少的那种尽可能多

换句话说，我们需要：

在图中保留 $N-1$ 条边，使编号 $1 \sim K$ 的子图始终连通，并最大化保留边中三种颜色的最小值 $\min{X, Y, Z}$（分别为白、绿、蓝）。

输入格式

第 $1$ 行两个整数 $N$ 和 $M$

接下来的 $M$ 行，每行三个整数 $A\ B\ C$，表示碎片 $A$ 和 $B$ 之间有一条颜色为 $C$ 的绳子（$0 \leq C \leq 2$）

保证输入初始图满足条件：对于任意 $2 \leq K \leq N$，编号 $1 \sim K$ 的点子图始终连通。

输出格式

输出一个整数，表示在保留 $N-1$ 条边的同时，三种颜色的最小数量 $\min{X, Y, Z}$ 的最大值。

10 13
1 2 0
2 3 1
2 4 2
4 5 0
4 6 2
6 7 1
4 7 0
7 8 1
7 9 0
7 10 1
8 9 2
9 10 0
3 8 2

3