#include<vector>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
#define N 6005
#define INF 1000000000
using namespace std;
struct edge
{
	int to,val;
};
struct node
{
	int id,val;
	bool operator < (const node &a) const
	{
		return val>a.val;
	}
};
vector<edge> e[N*2];
int n,m,dis[N][N],vis[N],num[N],ans;
void AddEdge(int u,int v,int w)
{
	edge edg=(edge){v,w};
	e[u].push_back(edg);
}
bool Spfa(int s)
{
	queue<int> q;
	q.push(s);
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s][s]=0;
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto i:e[u])
		{
			int v=i.to;
			int w=i.val;
			if(dis[s][u]+w<dis[s][v])
			{
				dis[s][v]=dis[s][u]+w;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
					num[v]++;
				}
				if(num[v]==n+1)
				{
					return 0;
				}
			}
		}
	}
	return 1;
}
void Heap_Dijkstra(int s)
{
	memset(vis,0,sizeof(vis));
	priority_queue<node> q;
	dis[s][s]=0;
	q.push((node){s,dis[s][s]});
	while(!q.empty())
	{
		int u=q.top().id;
		q.pop();
		if(vis[u])
		{
			continue;
		}
		vis[u]=1;
		for(auto i:e[u])
		{
			int v=i.to;
			int w=i.val;
			if(dis[s][u]+w<dis[s][v])
			{
				dis[s][v]=dis[s][u]+w;
				if(!vis[v])
				{
					q.push((node){v,dis[s][v]});
				}
			}
		}
	}
}
void Johnson()
{
	for(int u=1;u<=n;u++)
	{
		AddEdge(0,u,0);
	}
	if(!Spfa(0))
	{
		printf("-1\n");
		return;
	}
	for(int u=1;u<=n;u++)
	{
		for(auto &i:e[u])
		{
			int v=i.to;
			i.val+=dis[0][u]-dis[0][v];
		}
	}
	for(int i=1;i<=n;i++)
	{
		Heap_Dijkstra(i);
	}
	for(int i=1;i<=n;i++)
	{
		ans=0;
		for(int j=1;j<=n;j++)
		{
			if(dis[i][j]>=INF)
			{
				ans+=(LL)j*(LL)INF;
			}
			else
			{
				ans+=(LL)j*((LL)dis[i][j]+(LL)dis[0][j]-(LL)dis[0][i]);
			}
		}
		printf("%lld\n",ans);
	}
}
int main()
{
	freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);
	int u,v,w;
	while(m--)
	{
		scanf("%d%d%d",&u,&v,&w);
		AddEdge(u,v,w);
	}
	Johnson();
	return 0;
}