题目描述

假如你是 LZ ，你在知道了 MJZ 不可告人的秘密之不幸被 MJZ 抓住了。

经过一番激♂烈的搏斗，你被带到了 MJZ 的洞穴里，MJZ 的洞穴由 $n$ 个不连通的房间组成，编号为 $1, 2, ..., n$ 。MJZ 决定给你一次机会，如果你帮他在洞穴里修建通道，他就不吃你。

MJZ 已经告诉了你哪些房间之间可以修建通道，以及修建每条通道的代价，你需要选择其中的一些通道修建，使得所有房间都直接或间接通过通道连通，并且修建通道的总代价最小。

此外，在满足修建通道总代价最小的前提下，MJZ 还有一个要求：直接连接 $1$ 号房间的通道要尽可能多，因为 $1$ 号房间是餐厅，这样修建可以使 MJZ 吃饭方便一些。

修通道之前，你需要计算出在满足修建通道总代价最小的前提下，直接连接 $1$ 号房间的通道最多能有多少条。MJZ 的耐心是有限的，所以如果程序TLE的话，MJZ 就会在 $1$ 号房间吃掉你 ^_^

输入格式

第一行两个正整数 $n,\ m$ ，分别表示房间的个数和候选通道的个数。

接下来 $m$ 行，每行三个整数 $u,\ v,\ w$ ，表示可以修建一条直接连接 $u$ 号房间和 $v$ 号房间的通道，修建这条通道的代价为 $w$ 。

数据保证一定有方案使得所有房间都直接或间接通过通道连通。

输出格式

输出一个非负整数，表示在满足修建通道总代价最小的前提下，直接连接 $1$ 号房间的通道最多能有多少条。

样例

样例输入1

3 3
1 2 1
1 3 1
2 3 1

样例输出1

2

样例输入2

3 3
1 2 2
1 3 2
2 3 1

样例输出2

1

数据范围与提示

$1 \le n \le 2 \cdot 10^5$

$n - 1 \le m \le 2 \cdot 10^5$

$1 \le w \le 10^4$

$1 \le u,\ v \le n$