Description
C国有n座城市，城市之间通过m条单向道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。
Input
第一行包含两个正整数n、m
接下来m行每行包含三个正整数u、v、w，表示有一条从u到v长度为w的道路
n≤1500、m≤5000、w≤10000
Output
输出应有m行，第i行包含一个数，代表经过第i条道路的最短路的数目对1000000007取模后的结果
Sample Input
4 4
1 2 5
2 3 5
3 4 5
1 4 8
Sample Output
2
3
2
1
首先对于每个点求一次SPFA或dijkstra，然后标记出最短路上的边，对其进行拓扑排序，求出一条边的出点能到达的点能经过的最短路的个数，能到达这条边的入点的最短路的个数，然后使用乘法原理即可
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=1.5e3,M=5e3,mod=1e9+7;
struct S1{
#define ls (p<<1)
#define rs (p<<1|1)
#define fa (p>>1)
struct node{
int x,v;
bool operator <(const node &a)const{return v<a.v;}
}Q[N+10];
int tot;
void clear(){tot=0;}
void insert(int x,int v){
Q[++tot]=(node){x,v};
int p=tot;
while (p!=1&&Q[p]<Q[fa]) swap(Q[p],Q[fa]),p=fa;
}
void Delete(){
Q[1]=Q[tot--];
int p=1,son;
while (ls<=tot){
if (rs>tot||Q[ls]<Q[rs]) son=ls;
else son=rs;
if (Q[son]<Q[p]) swap(Q[p],Q[son]),p=son;
else break;
}
}
}Heap;
int pre[M+10],now[N+10],child[M+10],val[M+10],from[M+10];
int deep[N+10],cnt[N+10],h[N+10];
int Ans[M+10],cnt1[N+10],cnt2[N+10];
bool vis[N+10],can[M+10];
int n,m,tot;
void join(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,from[tot]=x,child[tot]=y,val[tot]=z;}
void dijkstra(int x){
memset(vis,0,sizeof(vis));
memset(deep,63,sizeof(deep));
Heap.clear(),Heap.insert(x,deep[x]=0);
while (Heap.tot){
int Now=Heap.Q[1].x;
Heap.Delete();
if (vis[Now]) continue;
vis[Now]=1;
for (int p=now[Now],son=child[p];p;p=pre[p],son=child[p]){
if (deep[son]>deep[Now]+val[p]){
deep[son]=deep[Now]+val[p];
Heap.insert(son,deep[son]);
}
}
}
memset(can,0,sizeof(can));
//记录最短路上的边
for (int i=1;i<=m;i++) if (deep[from[i]]+val[i]==deep[child[i]]) can[i]=1;
}
void topo(int x){//拓扑排序
memset(cnt,0,sizeof(cnt));
memset(cnt1,0,sizeof(cnt1));
memset(cnt2,0,sizeof(cnt2));
for (int i=1;i<=m;i++) if (can[i]) cnt[child[i]]++;
int head=1,tail=1;
cnt1[h[1]=x]=1;
for (;head<=tail;head++){
int Now=h[head];
for (int p=now[Now],son=child[p];p;p=pre[p],son=child[p]){
if (!can[p]) continue;
cnt1[son]=(cnt1[son]+cnt1[Now])%mod;
if (!(--cnt[son])) h[++tail]=son;
}
}
for (int i=tail,Now;i;i--){
cnt2[Now=h[i]]++;
for (int p=now[Now],son=child[p];p;p=pre[p],son=child[p]){
if (!can[p]) continue;
cnt2[Now]=(cnt2[Now]+cnt2[son])%mod;
}
}
}
void work(int x){
dijkstra(x),topo(x);
for (int i=1;i<=m;i++) if (can[i]) Ans[i]=(Ans[i]+1ll*cnt1[from[i]]*cnt2[child[i]]%mod)%mod;
}
int main(){
n=read(),m=read();
for (int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
join(x,y,z);
}
for (int i=1;i<=n;i++) work(i);
for (int i=1;i<=m;i++) printf("%d
",Ans[i]);
return 0;
}