#include<bits/stdc++.h>
#define INF 1000000000 //
using namespace std;
long long head[7005], vis[7005], t[7005],wei[7005],vet[7005], nxt[7005];
long long edge, n, m, u, v, w;
long long h[7005], dis[7005];
//long long INF=1000000000;
struct node {
  int dis, id;
  bool operator<(const node& a) const { return dis > a.dis; }
  node(int x, int d) { dis = d, id = x; }
};
void add(int x,int y,int w)
{
	edge++;
	vet[edge]=y;
	wei[edge]=w;
	nxt[edge]=head[x];
	head[x]=edge;
}
void dijkstra(int s)
{
	priority_queue<node>que;
	for(int i=1;i<=n;i++)dis[i]=INF;
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	que.push(node(s,0));
	while(!que.empty())
	{
		u=que.top().id;
		que.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=nxt[i])
		{
			v=vet[i];
			if(dis[v]>dis[u]+wei[i])
			{
				dis[v]=dis[u]+wei[i];
				if(!vis[v])
				{
					que.push(node(v,dis[v]));
				}
			}
		}
	}
}

bool spfa(int s)
{
	queue<int> q;
	memset(h,63,sizeof(h));
	h[s]=0;vis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=nxt[i])
		{
			v=vet[i];
			if(h[v]>h[u]+wei[i])
			{
				h[v]=h[u]+wei[i];
				if(!vis[v])
				{ 
					vis[v]=1;
					q.push(v);
					t[v]++;
					if(t[v]>=n+1)return false;
				}
			}
		}
	}	
	return true;
} 
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w);
	}
	for(int i=1;i<=n;i++)add(0,i,0);
	if(!spfa(0))
	{
		printf("-1\n");
		return 0;
	}
	else
	{
		for(int u=1;u<=n;u++)
			for(int i=head[u];i;i=nxt[i])wei[i]+=h[u]-h[vet[i]];
		for(int i=1;i<=n;i++)
		{
			dijkstra(i);
			long long ans=0;
			for(int j=1;j<=n;j++)
			{
				if(dis[j]==INF)
					ans+=1ll*j*INF;
				else ans+=1ll*j*(dis[j]+h[j]-h[i]);
			}
			printf("%lld\n",ans);
		}
	} 
	return 0;	
}