跑 $n$ 遍dij的做法，全Wa

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
typedef long long LL;
const int N=1505,M=5005,MOD=1e9+7;

int fst[N],nxt[M<<1],T[M<<1],W[M<<1],tot;
void add_edge(int a,int b,int c){nxt[++tot]=fst[a];fst[a]=tot;T[tot]=b;W[tot]=c;}

int n,m;
int dis[N], ans[M<<1];
bool inque[N];
int fa[N],lst[N],val[N]; 
int deg[N];

void dij(int p){
	priority_queue<PII,vector<PII>,greater<PII> > Q;
	memset(dis,0x3f,sizeof(dis));
	memset(inque,0,sizeof(inque));
	memset(fa,0,sizeof(fa));
	memset(lst,0,sizeof(lst));
	memset(val,0x3f,sizeof(val));
	memset(deg,0,sizeof(deg));
	
	dis[p]=0;
	Q.push({0,p});
	while(Q.size()){
		auto t=Q.top(); Q.pop();
		int x=t.second;
		if(inque[x]) continue;
		inque[x]=1;
		for(int i=fst[x];i;i=nxt[i]){
			int j=T[i];
			if(dis[j]==dis[x]+W[i]){
				if(W[i]<val[j]){
					deg[fa[j]]--;
					fa[j]=x; lst[j]=i; val[j]=W[i];
					deg[x]++;
				}
			}
			else if(dis[j]>dis[x]+W[i]){
				fa[j]=x; lst[j]=i; val[j]=W[i];
				deg[x]++;
				dis[j]=dis[x]+W[i];
				if(!inque[j]) Q.push({dis[j],j});
			}
		}
	}
}

void bfs(){
//	cout<<"\n";
//	for(int i=1;i<=n;i++) cout<<i<<" "<<fa[i]<<" "<<deg[i]<<"\n";
//	cout<<"\n";
	queue<PII> Q;
	for(int i=1;i<=n;i++)
		if(!deg[i])
			Q.push({i,1});
	while(Q.size()){
		auto t=Q.front(); Q.pop();
		int nw=t.first, dep=t.second;
		ans[lst[nw]]=(ans[lst[nw]]+dep)%MOD; 
		deg[fa[nw]]--;
		if(!deg[fa[nw]]){
			dep++;
			Q.push({fa[nw],dep});
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	
	for(int i=1;i<=n;i++){
		dij(i);
		bfs();
	}
	
	for(int i=1;i<=tot;i+=2)
		printf("%d\n",(ans[i]+ans[i+1])%MOD);
	return 0;
}