#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
int n,m;
int head[int(3e3)+10],st[int(6e3)+10],to[int(6e3)+10],val[int(6e3)+10],nxt[int(6e3)+10],tot;
int f[int(3e3)+10];
void add(int u,int v,int w){
	st[++tot]=u,to[tot]=v,val[tot]=w;
	nxt[tot]=head[u];
	head[u]=tot;
}
bool bellman(){
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=tot;j++)
			f[to[j]]=min(f[to[j]],f[st[j]]+val[j]);
	for(int j=1;j<=tot;j++)
		if(f[to[j]]>f[st[j]]+val[j])
			return false;
	return true;
}
int dis[int(3e3)+10][int(3e3)+10];
bool vis[int(3e3)+10];
priority_queue<PII,vector<PII>,greater<PII> >q;
void dij(int st){
	memset(vis,0,sizeof vis);
	dis[st][st]=0;
	q.push({0,st});
	while(!q.empty()){
		PII u=q.top();
		q.pop();
		int id=u.second,vl=u.first;
		if(vis[id]) continue;
		vis[id]=1;
		for(int i=head[id];i;i=nxt[i])
			if(dis[st][to[i]]>dis[st][id]+val[i])
				dis[st][to[i]]=dis[st][id]+val[i],q.push({dis[st][to[i]],to[i]});
	}
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int i=1;i<=n;i++)
		add(0,i,0);
	bool p=bellman();
	if(!p){
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=tot;i++)
		val[i]+=f[st[i]]-f[to[i]];
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=n;i++)
		dij(i);
	for(int i=1;i<=n;i++){
		long long ans=0;
		for(long long j=1;j<=n;j++)
			if(dis[i][j]>=90000000)
				ans+=j*100000000;
			else
				ans+=j*(dis[i][j]+f[j]-f[i]);
		cout<<ans<<"\n";
	}
	return 0;
}