#include<bits/stdc++.h>
using namespace std;
long long n,m,dis[1000001],h[1000001],num_edge,head[1000001],sum[1000001];
bool b[1000001],vis[1000001];
struct node{
	int dis,next,to;
}edge[1000001];
struct point{
	int pos,cur;
	bool operator < (const point & x) const
	{
		return x.pos < pos;
	}
};
void add(int from,int to,int dis)
{
	edge[++num_edge]=(node){dis,head[from],to};
	head[from]=num_edge;
}
bool spfa(int s)
{
	for(int i=1;i<=n;i++) h[i]=INT_MAX;
	queue<int>q;
	h[s]=0;
	b[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		b[u]=0;
		for(int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].to,d=edge[i].dis;
			if(h[v]>h[u]+d)
			{
				h[v]=h[u]+d;
				if(!b[v])
				{
					sum[v]++;
					if(sum[v]>=n) return 1;
					q.push(v);
					b[v]=1;
				}
			}
		}
	}
	return 0;
}
void dijkstra(int s)
{
	priority_queue<point>q;
	for(int i=1;i<=n;i++) dis[i]=INT_MAX,vis[i]=0;
	dis[s]=0;
	vis[s]=1;
	q.push((point){0,s});
	while(!q.empty())
	{
		point t=q.top();
		q.pop();
		int x=t.cur;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=edge[i].next)
		{
			int u=edge[i].to;
			if(dis[u]>dis[x]+edge[i].dis)
			{
				dis[u]=dis[x]+edge[i].dis;
				if(!vis[u]) q.push((point){dis[u],u});
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,d;
		scanf("%d%d%d",&u,&v,&d);
		add(u,v,d);
	}
	for(int i=1;i<=n;i++) add(0,i,0);
	if(spfa(0))
	{
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;i++)
		for(int j=head[i];j;j=edge[j].next) edge[j].dis+=h[i]-h[edge[j].to];
	for(int i=1;i<=n;i++)
	{
		dijkstra(i);
		long long ans=0;
		for(int j=1;j<=n;j++)
			if(dis[j]==INT_MAX) ans+=j*1e9;
			else ans+=j*(dis[j]+h[j]-h[i]);
		cout<<ans<<endl;
	}
}