60分4个WA求条

#include <iostream>
#include <cstring>
#include <bitset>
#include <queue>

using namespace std;

inline char getch()
{
	static char buf[100005], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100005, stdin), p1 == p2) ? EOF : *p1 ++ ;
}
template<typename Type>
inline void read(Type &x)
{
	char c; bool t;
	x = t = 0, c = getch();
	while (c < '0' || c > '9') t |= (c == '-'), c = getch();
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getch();
	x = t ? -x : x;
}

const int N = 2e3 + 5, M = 5e3 + 5;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;

int to[M], we[M], ne[M];
int head[N], pre[M], idx;
int n, m, dist[N];
int q[N], tt, res[N];
int in[N], out[N]; // s~i  i~...
bitset<M> tag;

void add(int u, int v, int w)
{
	pre[ ++ idx] = u;
	to[idx] = v;
	we[idx] = w;
	ne[idx] = head[u];
	head[u] = idx;
}

priority_queue<pii, vector<pii>, greater<pii>> p;
bitset<N> st;
void Dijkstra(int s)
{
	memset(dist, 0x3f, sizeof dist);
	st.reset();
	tt = 0;

	while (!p.empty()) p.pop();
	dist[s] = 0;
	p.push(pii{0, s});

	while (!p.empty())
	{
		int ver = p.top().second;
		p.pop();

		if (st[ver]) continue;
		st[ver] = true;

		q[ ++ tt] = ver;

		for (int i = head[ver]; i; i = ne[i])
		{
			int v = to[i], w = we[i];
			if (dist[v] > dist[ver] + w)
			{
				dist[v] = dist[ver] + w;
				p.push(pii{dist[v], v});
			}
		}
	}
}

void Toposort(int s)
{
	for (int i = 1; i <= n; i = -~ i) out[i] = in[i] = 0;
	tag.reset();
	for (int i = 1; i <= m; i = -~ i)
	{
		if (dist[pre[i]] + we[i] == dist[to[i]])
		{
			tag[i] = true;
		}
	}
	for (int i = tt; i >= 1; -- i)
	{
		for (int j = head[q[i]]; j; j = ne[j])
		{
			if (tag[j]) out[q[i]] += out[to[j]];
		}
		out[q[i]] ++ ; // form me to myself
	}
	in[s] = 1; // from me to myself
	for (int i = 1; i <= tt; i = -~ i)
	{
		for (int j = head[q[i]]; j; j = ne[j])
		{
			if (tag[j]) in[to[j]] += in[q[i]];
		}
	}
	for (int i = 1; i <= m; i = -~ i)
	{
		if (tag[i]) res[i] += 1ll * max(1, in[pre[i]]) * max(1, out[to[i]]) % mod, res[i] %= mod;
	}
}

int main()
{
	read(n), read(m);
	for (int i = 1; i <= m; i = -~ i)
	{
		int u, v, w;
		read(u), read(v), read(w);
		add(u, v, w);
	}
	for (int i = 1; i <= n; i = -~ i)
	{
		Dijkstra(i);
		Toposort(i);
	}
	for (int i = 1; i <= m; i = -~ i) printf("%d\n", res[i]);
	return 0;
}