Description

磊神是杭州阔少，为了让自己在杭州的生活更加便利，他想修建一个铁路网，于是他将一张规划图交给了 jbgg 让他负责修路 。

图上有 $n$ 个地点和 $m$ 条线路，第 $i$ 条线路直接链接地点 $a_i$ 和 $b_i$，长度为 $c_i$。

但由于磊神长期压榨 jbgg，不给发工资，jbgg 快吃不起饭了，jbgg 只好偷偷删掉一些线路偷拿预算吃饭。

但为了不让磊神发现，删掉线路之后的铁路网要满足如下条件：

• 原先能相互到达的两个地点仍能通过铁路相互到达。
• 任意两个地点之间的最短距离不变。

Format

Input

第一行两个正整数 $ n,m (2\leqslant n \leqslant 300, n-1 \leqslant m \leqslant \frac{n(n-1)}{2}) $，分别表示地点数量和线路数量。

接下来 $m$行，每行三个正整数 $ a_i,b_i,c_i (1 \leqslant a_i,b_i\leqslant n, 1 \leqslant c_i \leqslant 10^9) $，分别表示第 $i$ 条线路连接的两个地点和线路长度。

Output

一个整数，表示最多能删多少条线路。

Samples

3 3
1 2 5
2 1 3
1 3 6

1

4 9
1 2 5
2 1 3
1 3 6
3 2 4
3 1 2
4 3 8
4 2 1
4 1 5
4 4 9

5

提示

第一个样例中，删去第一条边后不会影响各点之间的最短距离，同时各点之间仍然联通。