RT

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll MAXN=2e4+3,INF=1000000000ll;
int n,m,s,tot,cnt[MAXN],head[MAXN];
ll dist[MAXN],f[MAXN];
bool flag[MAXN];
struct Edge{
    int next,to,w;
}g[MAXN];
inline int read(){
	int now=0,nev=1; char c=getchar();
	while(c<'0' || c>'9') { if(c=='-') nev=-1; c=getchar();}
	while(c>='0' && c<='9') { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
	return now*nev;
}
inline void write(ll x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
void add(int u,int v,int w){
    g[tot].to=v;
    g[tot].w=w;
    g[tot].next=head[u];
    head[u]=tot++;
    return ;
}
void dijkstra(int x){
    priority_queue<PII,vector<PII>,greater<PII>> q;
    while(!q.empty()) q.pop();
    for (int i=1;i<=n;i++) f[i]=INF;
    memset(flag,0,sizeof(flag));
    f[x]=0;
    q.push({0,x});
    while(!q.empty()){
        PII t=q.top();q.pop();
        int dis=t.first,id=t.second;
        if (flag[dis]) continue;
        for (int i=head[id];i!=-1;i=g[i].next){
            int j=g[i].to;
            if (f[j]>g[i].w+dis){
                f[j]=g[i].w+dis;
                q.push({f[j],j});
            }
        }
    }
    return ;
}
bool spfa(int x){
    memset(flag,0,sizeof(flag));
    queue<int> q;
    while(!q.empty()) q.pop();
    for (int i=1;i<=n;i++) dist[i]=INF;
    flag[x]=true;
    q.push(x);
    dist[x]=0;
    while(!q.empty()){
        int t=q.front();q.pop();
        flag[t]=false;
        for (int i=head[t];i!=-1;i=g[i].next){
            int j=g[i].to;
            if (dist[j]>dist[t]+g[i].w){
                dist[j]=dist[t]+g[i].w;
                cnt[j]=cnt[t]+1;
                if (cnt[j]>=n+1) return true;
                if (!flag[j]){
                    q.push(j);
                    flag[j]=true;
                }
            }
        }
    }
    return false;
}
int main(){
    memset(head,-1,sizeof(head));
    n=read();m=read();
    for (int i=0;i<m;i++){
        int a,b,c;
        a=read();b=read();c=read();
        add(a,b,c);
    }
    for (int i=1;i<=n;i++)
        add(0,i,0); //超级源点
    if (spfa(0)){
        printf("-1");
        return 0;
    }
    for (int i=1;i<=n;i++)
        for (int j=head[i];j!=-1;j=g[j].next)
            g[j].w+=dist[i]-dist[g[j].to];
    for (int i=1;i<=n;i++){
        ll ans=0;
        dijkstra(i);
        for (int j=1;j<=n;j++){
            if (f[j]==INF)
                ans+=j*INF;
            else
                ans+=j*(f[j]+dist[j]-dist[i]);
        }
        write(ans);puts("");
    }
    return 0;
}