#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
//~ #define int ll
#define pii pair<int,int>
#define fi first
#define se second
#define MP make_pair
#define pb push_back
using namespace std;
const int Inf=1e9;
const int N=2e3+10,M=1e6+10,mod=998244353;
vector<pii> e[N];
vector<int> G[N],eg[N];
int n,m,d[N],deg[N];
bool vis[N];
bitset<N> b[N],g[N],f[N];
priority_queue<pii,vector<pii> ,greater<pii> > q;
void dij(int s){
	for(int i=1;i<=n;i++) d[i]=Inf,G[i].clear(),eg[i].clear(),deg[i]=0;
	q.push(MP(0,s));
	d[s]=0;
	for(int i=1;i<=n;i++) vis[i]=0;
	while(!q.empty()){
		pii x=q.top();q.pop();
		int u=x.se;
		if(vis[u]) continue;
		vis[u]=1;
		for(pii y:e[u]){
			int v=y.fi,w=y.se;
			if(d[v]>d[u]+w){
				G[v].clear(),G[v].pb(u);
				d[v]=d[u]+w;
				if(!vis[v]) q.push(MP(d[v],v));
			}
			else if(d[v]==d[u]+w){
				G[v].pb(u);
			}
		}
	}
}
signed main(){
//	freopen("ex_floyd2.in","r",stdin);
//	freopen("floyd.out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,e[u].pb(MP(v,w));
	for(int i=1;i<=n;i++) g[i][i]=1,f[i][i]=1;
	for(int u=1;u<=n;u++){
		dij(u);
		for(int i=1;i<=n;i++) if(d[i]==Inf){
			g[u][i]=f[i][u]=1;
		}
		for(pii x:e[u]){
			int v=x.fi,w=x.se;
			if(w==d[v]) g[u][v]=f[v][u]=1;
		}
	}
	for(int y=1;y<=n;y++){
		dij(y);
		for(int i=1;i<=n;i++){
			for(int v:G[i]) deg[i]++,eg[v].pb(i);
		}
		queue<int> q;
		for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
		for(int i=1;i<=n;i++) b[i].reset(),b[i][i]=1;
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int v:eg[u]){
				b[v]|=b[u];
				if(!--deg[v]) q.push(v);
			}
		}
		for(int z=1;z<=n;z++) if(!g[y][z]){
			g[y][z]=!((g[y]&f[z]&b[z]).none());
			f[z][y]=g[y][z];
		}
	}
	int ans=0;
	for(int y=1;y<=n;y++){
		for(int z=1;z<=n;z++){
			ans+=!g[y][z];
		}
	}
	cout<<ans<<'\n';
	return 0;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<std::pair<int, int>, std::allocator<std::pair<int, int> > >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::pair<int, int>]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/queue:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:157:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~