Description

给定一个N节点无向连通图，问最多可以删除多少条边，使得删除后的图，对于两个节点 U,V其最短路没有发生改变。

图中没有自环，没有重边

Format

Input

第一行给出N，M，分别代表点与边

接下来M行，描述这个图

N<=300

Output

如题

Samples

3 3
1 2 2
2 3 3
1 3 6

1