rt

#include <bits/stdc++.h>
#define INF 1000000000
#define N   60001

using namespace std;

int n;
int m;
int ecnt;
int head[N];
long long dis[N];
bool vis[N];
long long rdis[N];
struct {
    int start;
    int end;
    int value;
    int next;
    long long tmp;
} edge[4 * N];

void init(int num, int cnt) {
    for (int i = 1; i <= num; i++) {
        head[i] = -1;
        dis[i] = INF;
        vis[i] = false;
    }
    for (int i = 1; i <= cnt; i++) {
        edge[i].next = -1;
    }
}

void add(int start, int end, int value) {
    ++ecnt;
    edge[ecnt].start = start;
    edge[ecnt].next = head[start];
    edge[ecnt].end = end;
    edge[ecnt].value = value;
    head[start] = ecnt;
}

void dij(int s) {
    priority_queue< pair< int, int > > pri;
    pri.emplace(0, s);
    dis[s] = 0;
    rdis[s] = 0;
    while (!pri.empty()) {
        int tmp = pri.top().second;
        pri.pop();
        if (vis[tmp]) {
            continue;
        }
        vis[tmp] = true;
        for (int i = head[tmp]; i != -1; i = edge[i].next) {
            int point = edge[i].end;
            if (dis[point] > dis[tmp] + edge[i].tmp) {
                dis[point] = dis[tmp] + edge[i].tmp;
                rdis[point] = rdis[tmp] + edge[i].value;
                pri.push({-dis[point], point});
            }
        }
    }
}

void print() {
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += rdis[i] * i;
    }
    cout << ans << endl;
}

void clear() {
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
    }
    for (int i = 1; i <= n; i++) {
        rdis[i] = INF;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    init(N, 4 * N);
    for (int i = 1; i <= m; i++) {
        int start;
        int end;
        int value;
        scanf("%d%d%d", &start, &end, &value);
        add(start, end, value);
    }
    for (int i = 1; i <= n; i++) {
        add(n + 1, i, 0);
    }
    clear();
    dis[n + 1] = 0;
    for (int j = 1; j <= n; ++j) {
        int check = 0;
        for (int i = 1; i <= ecnt; ++i) {
            if (dis[edge[i].start] != INF &&
                dis[edge[i].start] + edge[i].value <
                    dis[edge[i].end])  // relax
            {
                dis[edge[i].end] =
                    dis[edge[i].start] + edge[i].value;
                check = 1;
            }
        }

        if (check == 0) {
            break;
        }
    }

    bool flag = false;
    for (int i = 1; i <= ecnt; ++i) {
        if (dis[edge[i].start] + edge[i].value <
            dis[edge[i].end]) {
            flag = true;
        }
    }
    if (flag) {
        cout << -1;
        return 0;
    }
    for (int i = 1; i <= m; i++) {
        edge[i].tmp = edge[i].value + dis[edge[i].start] -
                      dis[edge[i].end];
    }
    for (int i = 1; i <= n; i++) {
        clear();
        dij(i);
        print();
    }
    return 0;
}