不管怎么说，双倍经验。
题意很简洁了。
对于每个源点 \(s\)，先跑一遍 dijkstra。显然，若满足 \(dis_v=dis_u+w_{u,v}\)，则 \(e(u,v)\) 一定在最短路上。
显然在 \(w_{u,v}>0\) 时，不存在 \(u,v\) 使得 \(dis_u=dis_v+w_{u,v} \wedge dis_v=dis_u+w_{u,v}\)。
因此，若将最短路径上的点从原图中取出，加入集合 \(V\)，其构成的图一定为 DAG \(G(V,E)\)。
可以考虑将其进行拓扑排序。
一般来说是可以在 dijkstra 中排序的。但是如果你硬要再写一遍也没人拦你
然后捏？
图上 dp。
设 \(G(V,E)\) 的源点（集）为 \(s'\)，汇点（集）为 \(t'\)。
对于任意 \(E_i:e(u,v)\)，设 \(out_i\) 为 \(s'\to u\) 的方案数，\(in_i\) 为 \(v\to t'\) 的方案数。
根据乘法原理，得 \(ans_i=in_i\times out_i\)。
\(out_i\) 好求。转移方程为 \(out_u=out_u+out_v[dis_u+w_{u,v}=dis_v]\ \ e(u,v)\in E\)。
事实上 \(in_i\) 和 \(out_i\) 的求法是一样的。
将 \(v\to t'\) 这部分建个反图 \(G'(V',E')\) 就可以达到同样的效果。
转移方程为 \(in_u=in_u+in_v[dis_v+w_{u,v}=dis_u]\ \ e(u,v)\in E'\)。
代码实现：
#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 15020, maxm = 50020;
const int inf = 998244853;
const int mod = 1e9 + 7;
class Solution {
struct Graph {
struct edge {
int u, v, w, next;
};
int head[maxn], idx;
edge e[maxm];
void add(int x, int y, int z) {
idx++; e[idx].u = x, e[idx].v = y, e[idx].w = z;
e[idx].next = head[x], head[x] = idx;
}
} G, revG;
struct point {
int u; ll dis;
point(int a, ll b) {u = a, dis = b;}
friend bool operator < (point a, point b) {
return a.dis > b.dis;
}
};
int n, m;
std::vector <int> route;
ll ans[maxn];
ll dis[maxn];
bool mk[maxn];
ll in[maxn], out[maxn];
void dijkstra(int st, Graph &G) {
std::priority_queue <point> q;
for(int i = 1; i <= n; i++) dis[i] = inf, mk[i] = 0;
dis[st] = 0, q.push(point(st, 0));
while(!q.empty()) {
int u = q.top().u; q.pop();
if(mk[u]) continue;
mk[u] = 1; route.push_back(u);
for(int j = G.head[u]; j; j = G.e[j].next) {
int v = G.e[j].v, w = G.e[j].w;
if(dis[v] > dis[u] + w) dis[v] = dis[u] + w, q.push(point(v, dis[v]));
}
}
}
void Count(int st) {
dijkstra(st, G);
for(int i = 1; i <= n; i++) in[i] = 0, out[i] = 0;
in[st] = 1;
for(auto v : route) {
for(int i = revG.head[v]; i; i = revG.e[i].next) {
int u = revG.e[i].v, w = revG.e[i].w;
if(dis[v] == dis[u] + w) in[v] += in[u], in[v] %= mod;
}
}
std::reverse(route.begin(), route.end());
for(auto u : route) {
out[u] = 1;
for(int i = G.head[u]; i; i = G.e[i].next) {
int v = G.e[i].v, w = G.e[i].w;
if(dis[v] == dis[u] + w) out[u] += out[v], out[u] %= mod;
}
}
route.clear();
for(int i = 1; i <= m; i++) {
int u = G.e[i].u, v = G.e[i].v, w = G.e[i].w;
if(dis[v] == dis[u] + w) ans[i] += std::max(1ll, in[u]) * std::max(1ll, out[v]), ans[i] %= mod;
}
}
public: void solve() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
G.add(u, v, w), revG.add(v, u, w);
}
for(int i = 1; i <= n; i++) Count(i);
for(int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
}
} S;
int main() {
S.solve();
return 0;
}