#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Title

### Problem Statement

You are given an undirected connected weighted graph with `N` vertices and `M` edges that contains neither self-loops nor double edges.

The `i`-th `(1≤i≤M)` edge connects vertex `a _{i}` and vertex

`b`with a distance of

_{i}`c`.

_{i}Here, a

*self-loop*is an edge where

`a`, and

_{i}= b_{i}(1≤i≤M)*double edges*are two edges where

`(a`or

_{i},b_{i})=(a_{j},b_{j})`(a`.

_{i},b_{i})=(b_{j},a_{j}) (1≤i<j≤M)A

*connected graph*is a graph where there is a path between every pair of different vertices.

Find the number of the edges that are not contained in any shortest path between any pair of different vertices.

### Constraints

`2≤N≤100``N-1≤M≤min(N(N-1)/2,1000)``1≤a`_{i},b_{i}≤N`1≤c`_{i}≤1000`c`is an integer._{i}- The given graph contains neither self-loops nor double edges.
- The given graph is connected.

### Input

The input is given from Standard Input in the following format:

NMa_{1}b_{1}c_{1}a_{2}b_{2}c_{2}:a_{M}b_{M}c_{M}

### Output

Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.

### Sample Input 1

3 3 1 2 1 1 3 1 2 3 3

### Sample Output 1

1

In the given graph, the shortest paths between all pairs of different vertices are as follows:

- The shortest path from vertex
`1`to vertex`2`is: vertex`1`→ vertex`2`, with the length of`1`. - The shortest path from vertex
`1`to vertex`3`is: vertex`1`→ vertex`3`, with the length of`1`. - The shortest path from vertex
`2`to vertex`1`is: vertex`2`→ vertex`1`, with the length of`1`. - The shortest path from vertex
`2`to vertex`3`is: vertex`2`→ vertex`1`→ vertex`3`, with the length of`2`. - The shortest path from vertex
`3`to vertex`1`is: vertex`3`→ vertex`1`, with the length of`1`. - The shortest path from vertex
`3`to vertex`2`is: vertex`3`→ vertex`1`→ vertex`2`, with the length of`2`.

Thus, the only edge that is not contained in any shortest path, is the edge of length `3` connecting vertex `2` and vertex `3`, hence the output should be `1`.

### Sample Input 2

3 2 1 2 1 2 3 1

### Sample Output 2

0

Every edge is contained in some shortest path between some pair of different vertices.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 19 | 1s | 256MB | Average |

2 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o longedge -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512