#include <bits/stdc++.h>
#define N 3000 + 5
#define M 6000 + 5 + N
using namespace std;
int n, m;
bool vis[N];
int head[N], to[M], v[M], nxt[M], idx, val[N], cnt[N];
int dv[N];
inline int add(int a, int b, int c) {
    to[++idx] = b, v[idx] = c, nxt[idx] = head[a], head[a] = idx;
}
inline int read() {
    char c = getchar();
    int w = 1, s = 0;
    while (c < '0' || c > '9') {
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        s = (s << 3) + (s << 1) + (c ^ 48);
        c = getchar();
    }
    return s * w;
}
inline void spfa() {
    queue<int> q;
    fill(val + 1, val + n + 1, 0x7fffffff);
    vis[0] = 1;
    val[0] = 0;
    q.push({0});
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; to[i]; i = nxt[i]) {
            if(val[to[i]] > val[u] + v[i]) {
                val[to[i]] = val[u] + v[i];
                if(!vis[to[i]]) {
                    ++cnt[to[i]];
                    if(cnt[to[i]] > n) {
                        puts("-1");
                        exit(0);
                    }
                    vis[to[i]] = true;
                    q.push({to[i]});
                }
            }
        }
    }
}
inline void dijkstra(int d) {
    priority_queue<pair<int, int>> q;
    fill(vis + 1, vis + n + 1, false);
    fill(dv + 1, dv + n + 1, 1e9);
    dv[d] = 0;
    q.push({0, d});
    while(q.size()) {
        int u = q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u]; to[i]; i = nxt[i]) {
            if(dv[to[i]] >  dv[u] + v[i] && !vis[to[i]]) {
                dv[to[i]] = dv[u] + v[i];
                q.push({- dv[to[i]], to[i]});
            }
        }
    }
}
int main() {
    n = read(), m = read();
    fill(head + 1, head + n + 1, -1);
    for (int i = 1; i <= m; ++i) {
        int a = read(), b = read(), c = read();
        add(a, b, c);
    }
    for (int i = 1; i <= n; ++i) {
        add(0, i, 0);
    }
    spfa();
    for (int i = 1; i <= n; ++i) {
        for(int j = head[i]; to[j]; j = nxt[j]) {
            v[j] = v[j] + val[i] - val[to[j]];
        }
    }
    for(int i = 1; i <= n; ++i) {
        dijkstra(i);
        long long ans = 0;
        for(int j = 1; j <= n; ++j) {
            ans += dv[j] == 1e9 ? j * dv[j] : j * (dv[j] + val[j] - val[i]);
        }
        printf("%lld\n", ans);
    }
    
}

12个点全部RE求调