Solution

首先看数据范围比较有限，所以我们要计算每条路被做为最短路通过的次数，那么我们就可以分各个点进行处理。我们每次都枚举一个源点做为最短路的起点，求解最短路的话使用这样我们就可以求解出去各个点的最短长度，接下来我们就考虑一个最短路图的概念，我们通过求解得到的数组很显然如果是第一次显然这条边应该被填入最短路的图中，下次如果再次走到了点，并且，说明走当前这条边去到和之前去到的方式路径长度相同，说明最短路的方案变多了，并且这条边权为的边也是最短路图中的一条。

那么如果我们求到了以为起点的最短路图，我们如何求解在其中的每条边的出现次数呢？我们单独考虑这条边的次数，那么根据乘法定理，我们只需要知道从的方案数，再知道从去到后面每个点的最短路方案数之和，最后我们把这两个数做个乘法就是这条边在这次的计算次数。

那么如何求解从的次数呢，我们在的时候，初始化，其余都是，那么只需要把原图中的边做次累加即可。那么如何去找去到后面各个点的和？我们考虑对之前的最短路图建立反图，我们把做初始化，那么对反图中，那么对于反图中这个次数就是，注意这里我们图反掉了。

建立反图之后遍历反图我们选择拓扑排序，正序的数组我们在可以求解到，注意建反图的时候如果新的边进来了，但是的话要把曾经连立过的全部边都要去掉。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int N = 1500 + 7; //节点数
const int M = 5000 + 7; //路径数
int n, m;
int head1[N], head2[N], tot1 = 0, tot2 = 0;//前向星变量
struct Node {
    //int u; //起点
    int w; //权值
    int v, next;
} edge1[M], edge2[M];

void init() {
    ms(head2, 0);
    tot2 = 0;
}

void add1(int u, int v, int w) {
    //edge[tot].u = u;
    edge1[++tot1].v = v;
    edge1[tot1].w = w;
    edge1[tot1].next = head1[u];
    head1[u] = tot1;
}

void add2(int u, int v, int w) {
    //edge[tot].u = u;
    edge2[++tot2].v = v;
    edge2[tot2].w = w;
    edge2[tot2].next = head2[u];
    head2[u] = tot2;
}

ll ans[M], cnt1[N], cnt2[N];
bool vis[N];
int dis[N];
priority_queue<pai, vector<pai>, greater<pai> > pq;
void dijkstra(int s) {
    ms(dis, 0x3f); ms(vis, 0);
    ms(cnt1, 0); // 从S走最短路图去各个点的方案数
    cnt1[s] = 1;
    dis[s] = 0;
    pq.push({ 0,s });
    while (pq.size()) {
        int u = pq.top().second; pq.pop();
        if (vis[u])    continue;
        vis[u] = 1;
        for (int i = head1[u]; i; i = edge1[i].next) {
            int v = edge1[i].v, w = edge1[i].w;
            if (dis[v] == dis[u] + w) { // 最短路图中一条边
                add2(v, u, i); // 用前向星编号做权值，按照原图建反边，方便后面的反向拓扑排序
                cnt1[v] = (cnt1[v] + cnt1[u]) % MOD;
            }
            else if (dis[v] > dis[u] + w) {
                head2[v] = 0; // 清空之前v点连过的边
                add2(v, u, i);
                cnt1[v] = cnt1[u];
                dis[v] = dis[u] + w;
                pq.push({ dis[v],v });
            }
        }
    }
}

int du[N];
queue<int> q;
void tpsort() {
    fill(cnt2 + 1, cnt2 + 1 + n, 1);
    ms(du, 0);
    rep(u, 1, n) {
        for (int i = head2[u]; i; i = edge2[i].next)
            ++du[edge2[i].v];
    }
    rep(i, 1, n)
        if (!du[i])    q.push(i);
    while (q.size()) {
        int u = q.front();    q.pop();
        for (int i = head2[u]; i; i = edge2[i].next) {
            int v = edge2[i].v, id = edge2[i].w;
            cnt2[v] = (cnt2[v] + cnt2[u]) % MOD;
            ans[id] = (ans[id] + cnt1[v] * cnt2[u]) % MOD;
            --du[v];
            if (!du[v])    q.push(v);
        }
    }
}

void solve() {
    n = read(), m = read();
    rep(i, 1, m) {
        int u = read(), v = read(), w = read();
        add1(u, v, w);
    }
    rep(i, 1, n) {
        init();
        dijkstra(i);
        tpsort();
    }
    rep(i, 1, m)
        print(ans[i]);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}