#include <bits/stdc++.h>

typedef long long ll;
ll INF = 1000000000ll;
const int max_n = 5005;
const int max_m = 10005;
int cnt = 0;
int head[max_n] = {0};
int nxt[max_m];
int from[max_m];
int to[max_m];
int weights[max_n];
void add_edge(int u, int v, int w) {
    nxt[++cnt] = head[u];
    from[cnt] = u;
    to[cnt] = v;
    weights[cnt] = w;
    head[u] = cnt;
}

bool bellman_ford(int s, int n, int m, ll* dis) {
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
    }
    dis[s] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            int w = weights[j], f = from[j], t = to[j];
            if (dis[t] > dis[f] + w) {
                dis[t] = dis[f] + w;
            }
        }
    }
    for (int j = 1; j <= m; j++) {
        int w = weights[j], f = from[j], t = to[j];
        if (dis[t] > dis[f] + w) {
            return true;
        }
    }
    return false;
}

void dijkstra(int s, int n, ll* dis) {
    std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>, std::greater<std::pair<ll, int>>> q;
    int known[n + 1];
    for (int i = 1; i <= n; i++) {
        known[i] = false, dis[i] = INF;
    }
    q.emplace(0, s);
    dis[s] = 0;
    while(!q.empty()) {
        auto top = q.top();
        q.pop();
        if (!known[top.second]) {
            known[top.second] = true;
            for (int i = head[top.second]; i != 0; i = nxt[i]) {
                int to_node = to[i];
                // printf("top.first:%d top.second:%d i:%d to_node:%d w:%d ori_dis:%d new_dis:%d\n", top.first, top.second, i, to_node, weights[i], dis[to_node], dis[top.second] + weights[i]);
                if (!known[to_node] && dis[to_node] > dis[top.second] + weights[i]) {
                    dis[to_node] = dis[top.second] + weights[i];
                    q.emplace(dis[to_node], to_node);
                }
            }
        }
    }
}

ll adjusts[max_n];
ll dis[max_n];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(head, 0, sizeof(head));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
    }
    for (int i = 1; i <= n; i++) {
        add_edge(n + 1, i, 0);
    }
    bool contains_loop = bellman_ford(n + 1, n + 1, m + n, adjusts);
    if (contains_loop) {
        printf("-1\n");
    } else {
        // reweight
        for (int i = 1; i <= m; i++) {
            int f = from[i], t = to[i];
            weights[i] += (adjusts[f] - adjusts[t]);
        }

        for (int i = 1; i <= n; i++) {
            ll res = 0;
            dijkstra(i, n, dis);
            for (int j = 1; j <= n; j++) {
                // printf("dis:%lld\n", static_cast<ll>(dis[j] - (adjusts[i] - adjusts[j])));
                if (dis[j] == INF) {
                    res += (INF * j);
                } else {
                    res += ((dis[j] + adjusts[j] - adjusts[i]) * j);
                }
            }
            printf("%lld\n", res);
        }
    }

    return 0;
}