Given an undirected connected weighted graph with
N vertices and
M edges that contains neither loops nor double edges.
I-e (
\(1<=i<=M\)) edge connects vertex
ai and the vertex
bi at distance
ci. We will assume that the loop is an edge, where
\(a_i=b_i\) (
\(1<=i<= M\)), and double edges are two edges where
\((a_i,b_i)=(a_j,b_j) \) or
\((a_i,b_i)=(b_j,a_j)\) (
\(1<=i<j< ;=M\)). A connected graph is a graph in which there is a path between every pair of distinct vertices. Find the number of edges that do not belong to any shortest path between any pair of distinct vertices.< br />
Input
The first line specifies two integers
N and
M (
\(2<=N<=100\) ,
\(N-1<=M<=min(N \cdot (N-1)/2,1000)\)). This is followed by
M lines of three integers per line:
ai,
bi ,
ci (
\(1<=a_i, b_i<=N\)< /span>, \(1<=c_i<=1000\)). This graph does not contain loops or double edges. This graph is connected .
Imprint
Print the number of edges in the graph that do not belong to any shortest path between any pair of distinct vertices.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
3 3
1 2 1
1 3 1
2 3 3
|
1
|
In this graph, the shortest paths between all pairs of distinct vertices are:
Shortest path from node 1 to node 2: node 1 → vertex 2, path length is 1.
Shortest path from node 1 to node 3: node 1 → vertex 3, path length is 1.
Shortest path from node 2 to node 1: node 2 → vertex 1, path length is 1.
Shortest path from node 2 to node 3: node 2 → peak 1 → vertex 3, path length is 2.
Shortest path from node 3 to node 1: node 3 → vertex 1, path length is 1.
Shortest path from node 3 to node 2: node 3 → peak 1 → vertex 2, path length is 2.
So the only edge that is not contained in any shortest path is the edge of length 3 connecting vertex 2 and vertex 3, so the output should be 1. |
| 2 |
3 2
1 2 1
2 3 1
|
0
|
Each edge is contained in some shortest path between a pair of distinct vertices. |