#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define PB push_back
#define ALL(i_) i_.begin(), i_.end()
#define LOG2(x) (31 - __builtin_clz(x))
#define getBit(x, i) ((x >> i) & 1)
#define rd(l, r) (l + rng() % (r - l + 1))
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
template<class X, class Y> bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {
x = y;
return 1;
}
return 0;
}
template<class X, class Y> bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return 1;
}
return 0;
}
template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); }
const int mod = (int) 1e9 + 7;
const int oo = (int) 1e9 + 99;
const int maxn = (int) 1e5 + 11;
const int LOG = (int) 20;
struct data_{
int u, v, w;
int getNode(const int &x) const{
return (u ^ v ^ x);
}
} edges[5001];
int n, m;
vector<int> adj[1501];
vector<vector<int>> dp;
vector<int> f[1501], g[1501];
void Dijkstra(int sta, vector<int> &dp){
dp.resize(n + 1, oo);
dp[sta] = 0;
priority_queue<ii, vector<ii>, greater<ii>> que;
que.push({dp[sta], sta});
while(!que.empty()){
int u = que.top().second;
int du = que.top().first;
que.pop();
if(du != dp[u]) continue;
for(int &x : adj[u]){
int v = edges[x].getNode(u);
int w = edges[x].w;
if(minimize(dp[v], dp[u] + w)) que.push({dp[v], v});
}
}
// for(int i = 1; i <= n; i++) if(dp[i] != oo){
// f[sta].PB(i);
// g[i].PB(sta);
// }
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TASK "PATHS"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
cin >> n >> m;
dp.resize(n + 1);
for(int i = 1; i <= m; i++){
int u, v, w; cin >> u >> v >> w;
edges[i] = {u, v, w};
adj[u].PB(i);
}
for(int i = 1; i <= n; i++) Dijkstra(i, dp[i]);
for(int i = 1; i <= m; i++){
int u = edges[i].u;
int v = edges[i].v;
int w = edges[i].w;
int ans = 0;
for(int x = 1; x <= n; x++) for(int y = 1; y <= n; y++){
if(dp[x][u] + w + dp[v][y] == dp[x][y]){
++ans;
if(ans >= mod) ans -= mod;
}
}
cout << ans << "\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cm10MTk5Mzcgcm5nKGNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7CgojZGVmaW5lIFBCIHB1c2hfYmFjawojZGVmaW5lIEFMTChpXykgaV8uYmVnaW4oKSwgaV8uZW5kKCkKI2RlZmluZSBMT0cyKHgpICgzMSAtIF9fYnVpbHRpbl9jbHooeCkpCiNkZWZpbmUgZ2V0Qml0KHgsIGkpICgoeCA+PiBpKSAmIDEpCiNkZWZpbmUgcmQobCwgcikgKGwgKyBybmcoKSAlIChyIC0gbCArIDEpKQoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gaWk7Cgp0ZW1wbGF0ZTxjbGFzcyBYLCBjbGFzcyBZPiBib29sIG1pbmltaXplKFggJngsIGNvbnN0IFkgJnkpewogICAgWCBlcHMgPSAxZS05OwogICAgaWYgKHggPiB5ICsgZXBzKSB7CiAgICAgICAgeCA9IHk7CiAgICAgICAgcmV0dXJuIDE7CiAgICB9CiAgICByZXR1cm4gMDsKfQoKdGVtcGxhdGU8Y2xhc3MgWCwgY2xhc3MgWT4gYm9vbCBtYXhpbWl6ZShYICZ4LCBjb25zdCBZICZ5KSB7CiAgICBYIGVwcyA9IDFlLTk7CiAgICBpZiAoeCArIGVwcyA8IHkpIHsKICAgICAgICB4ID0geTsKICAgICAgICByZXR1cm4gMTsKICAgIH0KICAgIHJldHVybiAwOwp9Cgp0ZW1wbGF0ZTxjbGFzcyBUPiBUIEFicyhjb25zdCBUICZ4KSB7IHJldHVybiAoeCA8IDAgPyAteCA6IHgpOyB9Cgpjb25zdCBpbnQgbW9kID0gKGludCkgMWU5ICsgNzsKY29uc3QgaW50IG9vID0gKGludCkgMWU5ICsgOTk7CmNvbnN0IGludCBtYXhuID0gKGludCkgMWU1ICsgMTE7CmNvbnN0IGludCBMT0cgPSAoaW50KSAyMDsKCnN0cnVjdCBkYXRhX3sKICAgIGludCB1LCB2LCB3OwoKICAgIGludCBnZXROb2RlKGNvbnN0IGludCAmeCkgY29uc3R7CiAgICAgICAgcmV0dXJuICh1IF4gdiBeIHgpOwogICAgfQp9IGVkZ2VzWzUwMDFdOwoKaW50IG4sIG07CnZlY3RvcjxpbnQ+IGFkalsxNTAxXTsKdmVjdG9yPHZlY3RvcjxpbnQ+PiBkcDsKdmVjdG9yPGludD4gZlsxNTAxXSwgZ1sxNTAxXTsKCnZvaWQgRGlqa3N0cmEoaW50IHN0YSwgdmVjdG9yPGludD4gJmRwKXsKICAgIGRwLnJlc2l6ZShuICsgMSwgb28pOwogICAgZHBbc3RhXSA9IDA7CiAgICBwcmlvcml0eV9xdWV1ZTxpaSwgdmVjdG9yPGlpPiwgZ3JlYXRlcjxpaT4+IHF1ZTsKICAgIHF1ZS5wdXNoKHtkcFtzdGFdLCBzdGF9KTsKICAgIHdoaWxlKCFxdWUuZW1wdHkoKSl7CiAgICAgICAgaW50IHUgPSBxdWUudG9wKCkuc2Vjb25kOwogICAgICAgIGludCBkdSA9IHF1ZS50b3AoKS5maXJzdDsKICAgICAgICBxdWUucG9wKCk7CiAgICAgICAgaWYoZHUgIT0gZHBbdV0pIGNvbnRpbnVlOwogICAgICAgIGZvcihpbnQgJnggOiBhZGpbdV0pewogICAgICAgICAgICBpbnQgdiA9IGVkZ2VzW3hdLmdldE5vZGUodSk7CiAgICAgICAgICAgIGludCB3ID0gZWRnZXNbeF0udzsKICAgICAgICAgICAgaWYobWluaW1pemUoZHBbdl0sIGRwW3VdICsgdykpIHF1ZS5wdXNoKHtkcFt2XSwgdn0pOwogICAgICAgIH0KICAgIH0KLy8gICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspIGlmKGRwW2ldICE9IG9vKXsKLy8gICAgICAgIGZbc3RhXS5QQihpKTsKLy8gICAgICAgIGdbaV0uUEIoc3RhKTsKLy8gICAgfQp9CgppbnQgbWFpbigpewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsgY2luLnRpZSgwKTsgY291dC50aWUoMCk7CiAgICAjZGVmaW5lIFRBU0sgIlBBVEhTIgogICAgaWYoZm9wZW4oVEFTSyIuaW5wIiwgInIiKSkgewogICAgICAgIGZyZW9wZW4oVEFTSyIuaW5wIiwgInIiLCBzdGRpbik7CiAgICAgICAgZnJlb3BlbihUQVNLIi5vdXQiLCAidyIsIHN0ZG91dCk7CiAgICB9CiAgICBjaW4gPj4gbiA+PiBtOwogICAgZHAucmVzaXplKG4gKyAxKTsKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbTsgaSsrKXsKICAgICAgICBpbnQgdSwgdiwgdzsgY2luID4+IHUgPj4gdiA+PiB3OwogICAgICAgIGVkZ2VzW2ldID0ge3UsIHYsIHd9OwogICAgICAgIGFkalt1XS5QQihpKTsKICAgIH0KICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSBEaWprc3RyYShpLCBkcFtpXSk7CiAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG07IGkrKyl7CiAgICAgICAgaW50IHUgPSBlZGdlc1tpXS51OwogICAgICAgIGludCB2ID0gZWRnZXNbaV0udjsKICAgICAgICBpbnQgdyA9IGVkZ2VzW2ldLnc7CiAgICAgICAgaW50IGFucyA9IDA7CiAgICAgICAgZm9yKGludCB4ID0gMTsgeCA8PSBuOyB4KyspIGZvcihpbnQgeSA9IDE7IHkgPD0gbjsgeSsrKXsKICAgICAgICAgICAgaWYoZHBbeF1bdV0gKyB3ICsgZHBbdl1beV0gPT0gZHBbeF1beV0pewogICAgICAgICAgICAgICAgKythbnM7CiAgICAgICAgICAgICAgICBpZihhbnMgPj0gbW9kKSBhbnMgLT0gbW9kOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgYW5zIDw8ICJcbiI7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=