{"problem":{"name":"Candidates of No Shortest Paths","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc051_d"},"statements":[{"statement_type":"Markdown","content":"You are given an undirected connected weighted graph with $N$ vertices and $M$ edges that contains neither self-loops nor double edges.  \nThe $i$\\-th $(1≤i≤M)$ edge connects vertex $a_i$ and vertex $b_i$ with a distance of $c_i$.  \nHere, a _self-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)$.  \nA _connected graph_ is a graph where there is a path between every pair of different vertices.  \nFind the number of the edges that are not contained in any shortest path between any pair of different vertices.\n\n## Constraints\n\n*   $2≤N≤100$\n*   $N-1≤M≤min(N(N-1)/2,1000)$\n*   $1≤a_i,b_i≤N$\n*   $1≤c_i≤1000$\n*   $c_i$ is an integer.\n*   The given graph contains neither self-loops nor double edges.\n*   The given graph is connected.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$  \n$a_1$ $b_1$ $c_1$  \n$a_2$ $b_2$ $c_2$\n$:$  \n$a_M$ $b_M$ $c_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc051_d","tags":[],"sample_group":[["3 3\n1 2 1\n1 3 1\n2 3 3","1\n\nIn the given graph, the shortest paths between all pairs of different vertices are as follows:\n\n*   The shortest path from vertex $1$ to vertex $2$ is: vertex $1$ → vertex $2$, with the length of $1$.\n*   The shortest path from vertex $1$ to vertex $3$ is: vertex $1$ → vertex $3$, with the length of $1$.\n*   The shortest path from vertex $2$ to vertex $1$ is: vertex $2$ → vertex $1$, with the length of $1$.\n*   The shortest path from vertex $2$ to vertex $3$ is: vertex $2$ → vertex $1$ → vertex $3$, with the length of $2$.\n*   The shortest path from vertex $3$ to vertex $1$ is: vertex $3$ → vertex $1$, with the length of $1$.\n*   The shortest path from vertex $3$ to vertex $2$ is: vertex $3$ → vertex $1$ → vertex $2$, with the length of $2$.\n\nThus, 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$."],["3 2\n1 2 1\n2 3 1","0\n\nEvery edge is contained in some shortest path between some pair of different vertices."]],"created_at":"2026-03-03 11:01:14"}}