Home

Contest: Task: Related: TaskD TaskF

Score : $500$ points

Problem Statement

You are given a simple connected undirected graph with $N$ vertices and $M$ edges.
Edge $i$ connects Vertex $A_i$ and Vertex $B_i$, and has a length of $C_i$.

Let us delete some number of edges while satisfying the conditions below. Find the maximum number of edges that can be deleted.

The graph is still connected after the deletion.
For every pair of vertices $(s, t)$, the distance between $s$ and $t$ remains the same before and after the deletion.

Notes

A simple connected undirected graph is a graph that is simple and connected and has undirected edges.
A graph is simple when it has no self-loops and no multi-edges.
A graph is connected when, for every pair of two vertices $s$ and $t$, $t$ is reachable from $s$ by traversing edges.
The distance between Vertex $s$ and Vertex $t$ is the length of a shortest path between $s$ and $t$.

Constraints

$2 \leq N \leq 300$
$N-1 \leq M \leq \frac{N(N-1)}{2}$
$1 \leq A_i \lt B_i \leq N$
$1 \leq C_i \leq 10^9$
$(A_i, B_i) \neq (A_j, B_j)$ if $i \neq j$.
The given graph is connected.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$

Output

Print the answer.

Sample Input 1

Sample Output 1

The distance between each pair of vertices before the deletion is as follows.

The distance between Vertex $1$ and Vertex $2$ is $2$.
The distance between Vertex $1$ and Vertex $3$ is $5$.
The distance between Vertex $2$ and Vertex $3$ is $3$.

Deleting Edge $3$ does not affect the distance between any pair of vertices. It is impossible to delete two or more edges while satisfying the condition, so the answer is $1$.

Sample Input 2

Sample Output 2

No edge can be deleted.

Sample Input 3