模板题。

我们注意到，一条边是不是多余的，在于是否存在另一条路径比直接前往更短。

同时：因为数据很小，完全可以跑 $Floyd$ 多源最短路。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T = 1;
const int N = 300 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
int dis[N][N];

struct Edge {
	int u;
	int v;
	int w;
}edges[N * N];//注意

void Solve() {
	cin >> n >> m;
	memset(dis, INF, sizeof(dis));//这里一定不能填127
	for (int i = 1; i <= m; i++) {
		cin >> edges[i].u >> edges[i].v >> edges[i].w;
		dis[edges[i].u][edges[i].v] = edges[i].w;
		dis[edges[i].v][edges[i].u] = edges[i].w;
	}
	for (int i = 1; i <= n; i++) dis[i][i] = 0;
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j || i == k || j == k) continue;
				if (dis[i][k] + dis[k][j] < dis[i][j]) {
					dis[i][j] = dis[i][k] + dis[k][j];
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i++) {
		int u = edges[i].u, v = edges[i].v, w = edges[i].w;
		for (int k = 1; k <= n; k++) {
			if (k == u || k == v) continue;
			if (dis[u][k] + dis[k][v] <= w) {
				ans++;
				break;
			}
		}
	}
	cout << ans;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	while (T--) {
		Solve();
	}
	return 0;
}