辺 \(e\) を一つ固定する． \(e\) を残す条件，消す条件を考える．
基本的には，同じコストなら path は長い方を残すのが得と言える．
\(e = (a,b)\) を消すのは，
ある \(k \in V\) であって， \(k \not \in \{a,b\}\) かつ \(cost_{e} \leq cost_{a,k} + cost{k,b}\) であることと同値．
つまり，辺 \(e\) の上位互換である path があるとき， そのときに限り \(e\) を消す．
別解
Warshall-Floyd を使うのは同じ． コストの代わりに，(コスト，min cost の pathの長さの最大) を求める．
気持ちとしては，同じコストなら path が長い方が良いから．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n >> m;
vvll co(n, vll(n,INFL));
rep(i,m){
ll a,b,c; cin >> a >> b >> c;
--a,--b;
chmin(co[a][b], c);
chmin(co[b][a], c);
ed[i] = {a,b,c};
}
rep(i,n) chmin(co[i][i], 0LL);
rep(k,n) rep(cu,n) rep(ne,n) chmin(co[cu][ne], co[cu][k] + co[k][ne]);
ll ans = 0;
for(auto [a,b,c]: ed){
rep(i,n) if(a != i && i != b){
if(co[a][i] + co[i][b] <= c) { // i : 消す
ans ++;
break;
}
}
}
cout << ans << endl;
return 0;
}
