Description：

计算一个有向带权图中对于每一个边有多少条不同的最短路经过该道路。

$1\le n \le 1500,1\le m \le 5000$

Solution：

看这个数据范围应该是 $n^2\log n$ 的复杂度，也就是说应该是枚举每一个点求一次最短路，那么就不难想到对于每一个点求一次以它为出发点的最短路，具体做法是建出最短路图后记一个 $cnt1$ 表示从原点出发到这个点的最短路条数，拓扑排序 $DP$ 就行了，然后再记一个 $cnt2$ 表示从这个点出发的最短路，可以在反图上拓扑 $DP$ ，由于不要求到终点，所以初值是所有点都是一，代表路径可以在所有点截止，然后这次对边 $u\to v$ 的贡献是 $cnt1[u]\times cnt2[v]$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 1000000007

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m;

#define MAXN 1510

#define MAXM 5010

struct edge

{

	int to,nxt,v,id;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,int c,int d)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].id = d;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int d[MAXN];

bool v[MAXN];

inline void dijkstra(int s)

{

	memset(v,false,sizeof(v));

	memset(d,0x3f,sizeof(d));

	priority_queue< pair<int,int> > q;

	q.push(make_pair(0,s));d[s] = 0;

	while(!q.empty())

	{

		register int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		for(register int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	return;

}

vector<int> g[MAXN];

int ind[MAXN];

typedef long long ll;

ll cnt1[MAXN],cnt2[MAXN];

ll ans[MAXM];

inline void calc(int s)

{

	for(register int i = 1;i <= n;++i)g[i].clear();

	memset(ind,0,sizeof(ind));

	memset(cnt1,0,sizeof(cnt1));

	for(register int k = 1;k <= n;++k)

		for(register int i = lin[k];i != 0;i = e[i].nxt)

			if(d[k] + e[i].v == d[e[i].to])

				++ind[e[i].to];

	queue<int> q;

	q.push(s);cnt1[s] = 1;

	while(!q.empty())

	{

		register int k = q.front();q.pop();

		for(register int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] == d[k] + e[i].v)

			{

				cnt1[e[i].to] = (cnt1[e[i].to] + cnt1[k]) % MOD;

				g[e[i].to].push_back(k);

				--ind[e[i].to];

				if(ind[e[i].to] == 0)

				{

					q.push(e[i].to);

				}

			}

		}

	}

	for(register int k = 1;k <= n;++k)

		for(register int i = 0;i < g[k].size();++i)

			++ind[g[k][i]];

	for(register int k = 1;k <= n;++k)cnt2[k] = 1;

	for(register int k = 1;k <= n;++k)

		if(ind[k] == 0)

			q.push(k);

	while(!q.empty())

	{

		register int k = q.front();q.pop();

		for(register int i = 0;i < g[k].size();++i)

		{

			--ind[g[k][i]];

			cnt2[g[k][i]] = (cnt2[g[k][i]] + cnt2[k]) % MOD;

			if(ind[g[k][i]] == 0)

			{

				q.push(g[k][i]);

			}

		}

	}

	for(register int k = 1;k <= n;++k)

		for(register int i = lin[k];i != 0;i = e[i].nxt)

			if(d[k] + e[i].v == d[e[i].to])

				ans[e[i].id] = (ans[e[i].id] + cnt1[k] * cnt2[e[i].to] % MOD) % MOD;

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	register int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		a = read();b = read();c = read();

		add(a,b,c,i);

	}

	for(register int i = 1;i <= n;++i)

	{

		dijkstra(i);

		calc(i);

	}

	for(register int i = 1;i <= m;++i)printf("%lld\n",ans[i]);

	return 0;

}