#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct EDGE{
    ll y,len;

    EDGE(ll _y=0,ll _len=0):y(_y),len(_len){}
};

vector<EDGE> edge[3005];
ll n,m;
ll h[3005];

//Bellman_Ford专用
ll cnt[3005];
bool vis[3005];

//dijkstra专用
bool found[3005];
ll dis[3005][3005];
struct node{
    ll dis;
    ll v;

    node(ll _dis,ll _v):dis(_dis),v(_v){}

    bool operator<(const struct node &n) const{
        return dis>n.dis;
    }
};

bool Bellman_Ford(){
    memset(h,63,3005*sizeof(ll));
    queue<ll> q;

    h[0]=0;
    q.push(0);
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        vis[u]=false;

        for(ll i=0;i<edge[u].size();i++){
            ll v=edge[u][i].y;
            if(h[u]+edge[u][i].len<h[v]){
                h[v]=h[u]+edge[u][i].len;
                cnt[v]=cnt[u]+1;

                if(cnt[v]>=n+1) return false;

                if(!vis[v]){
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }

    return true;
}

bool init(){
    for(ll i=1;i<=n;i++){
        EDGE e(i,0);
        edge[0].push_back(e);
    }

    if(!Bellman_Ford()) return false;

    for(ll i=1;i<=n;i++){
        for(ll j=0;j<edge[i].size();j++){
            edge[i][j].len+=h[i]-h[edge[i][j].y];
            //cout << "u=" << i << " v=" << edge[i][j].y << " len=" << edge[i][j].len << endl;
        }
    }

    return true;
}

void dijkstra(ll s){
    memset(found,0,3005*sizeof(bool));
    memset(dis[s],0X3F,3005*sizeof(ll));
    priority_queue<node> q;

    dis[s][s]=0;
    node n(0,s);
    q.push(n);
    while(!q.empty()){
        ll u=q.top().v;
        q.pop();

        if(!found[u]){
            found[u]=true;

            for(ll i=0;i<edge[u].size();i++){
                ll v=edge[u][i].y;
                if(dis[s][u]+edge[u][i].len<dis[s][v]){
                    dis[s][v]=dis[s][u]+edge[u][i].len;
                    node n(dis[s][v],v);
                    q.push(n);
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(ll i=0;i<m;i++){
        ll x,y,len;
        cin >> x >> y >> len;
        EDGE e(y,len);
        edge[x].push_back(e);
    }

    if(init()){
        for(ll i=1;i<=n;i++){
            dijkstra(i);
        }

        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                if(dis[i][j]>300000){
                    dis[i][j]=1000000000;
                }else{
                    dis[i][j]-=h[i]-h[j];
                }
            }
        }

        for(ll i=1;i<=n;i++){
            ll ans=0;
            for(ll j=1;j<=n;j++) ans+=j*dis[i][j];

            cout << ans << endl;
        }
    }else{
        cout << -1 << endl;
    }
    return 0;
}