No submission language available for this problem.

Background

Special for beginners, ^_^

Description

flame 和 mybing 喜欢在一起玩益智游戏

现在他们拿到了一个益智游戏谜题：

他们有一张一共有 $n$ 个点，$m$ 条边的无重边无自环的连通带权无向图,

定义 $d(i,j)$ 是 $i$ 到 $j$ 的最短路径上的边权之和。 游戏的谜题是：

他们需要删除一些边,要求删完之后的图满足下列条件:

• 图仍然联通;
• 对于 $1≤i,j≤n$, 删边前的 $d(i,j)$ 等于删边后的 $d(i,j)$。 所以 mybing 和 flame 最多能删掉多少条边呢？

Format

Input

第一行两个整数 $n,m$

接下来 $m$ 行，每行三个整数 $x_i,y_i,w_i$ 表示有一条连接 $x_i,y_i$ 的无向边，边权为 $w_i$

Output

一行一个整数 $cnt$ ,表示他们能删掉的最大边数

Samples

3 3
1 2 2
2 3 3
1 3 6

1

5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10

5

Limitation

对于 $30\%$ 的数据，满足 $2\le n \le 6$

对于 $70\%$ 的数据，满足 $2\le n \le 300$

对于 $100\%$ 的数据，满足 $2\le n \le 500,n-1\le m \le \frac{n(n-1)}{2},1 \le x_i,y_i\le n,1\le w \le 10^9$

1s, 1024KiB for each test case.