{"problem":{"name":"Edge Deletion","description":{"content":"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 whil","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc243_e"},"statements":[{"statement_type":"Markdown","content":"You are given a simple connected undirected graph with $N$ vertices and $M$ edges.  \nEdge $i$ connects Vertex $A_i$ and Vertex $B_i$, and has a length of $C_i$.\nLet us delete some number of edges while satisfying the conditions below. Find the maximum number of edges that can be deleted.\n\n*   The graph is still connected after the deletion.\n*   For every pair of vertices $(s, t)$, the distance between $s$ and $t$ remains the same before and after the deletion.\n\n## Constraints\n\n*   $2 \\leq N \\leq 300$\n*   $N-1 \\leq M \\leq \\frac{N(N-1)}{2}$\n*   $1 \\leq A_i \\lt B_i \\leq N$\n*   $1 \\leq C_i \\leq 10^9$\n*   $(A_i, B_i) \\neq (A_j, B_j)$ if $i \\neq j$.\n*   The given graph is connected.\n*   All values in input are integers.\n\n## Input\n\nInput 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$\\vdots$\n$A_M$ $B_M$ $C_M$\n\n[samples]\n\n## Notes\n\nA simple connected undirected graph is a graph that is simple and connected and has undirected edges.  \nA graph is simple when it has no self-loops and no multi-edges.  \nA graph is connected when, for every pair of two vertices $s$ and $t$, $t$ is reachable from $s$ by traversing edges.  \nThe distance between Vertex $s$ and Vertex $t$ is the length of a shortest path between $s$ and $t$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc243_e","tags":[],"sample_group":[["3 3\n1 2 2\n2 3 3\n1 3 6","1\n\nThe distance between each pair of vertices before the deletion is as follows.\n\n*   The distance between Vertex $1$ and Vertex $2$ is $2$.\n*   The distance between Vertex $1$ and Vertex $3$ is $5$.\n*   The distance between Vertex $2$ and Vertex $3$ is $3$.\n\nDeleting 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$."],["5 4\n1 3 3\n2 3 9\n3 5 3\n4 5 3","0\n\nNo edge can be deleted."],["5 10\n1 2 71\n1 3 9\n1 4 82\n1 5 64\n2 3 22\n2 4 99\n2 5 1\n3 4 24\n3 5 18\n4 5 10","5"]],"created_at":"2026-03-03 11:01:14"}}