#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;
	long long val;
	bool operator < (const node &a) const
	{
		return val>a.val;
	}
};
vector<edge> e[N*2];
int n,m,vis[N],num[N];
long long h[N],dis[N];
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;
 	memset(h,0x3f,sizeof(h));
	memset(vis,0,sizeof(vis));
	h[s]=0;
	vis[s]=1;
	q.push(s);
	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(h[u]+w<h[v])
			{
				h[v]=h[u]+w;
				num[v]=num[u]+1;
				if(num[v]>n)
				{
					return 0;
				}
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return 1;
}
void Heap_Dijkstra(int s)
{
	priority_queue<node> q;
 	for(int i=1;i<=n;i++)
 	{
		dis[i]=INF;
	}
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	q.push((node){s,dis[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[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					q.push((node){v,dis[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+=h[u]-h[v];
		}
	}
	for(int i=1;i<=n;i++)
	{
		LL ans=0;//注释处<----------------------------------------
		Heap_Dijkstra(i);
		for(int j=1;j<=n;j++)
		{
			if(dis[j]>=(LL)INF)
			{
				ans+=(LL)j*(LL)INF;
			}
			else
			{
				ans+=(LL)j*((LL)dis[j]+(LL)h[j]-(LL)h[i]);
			}
		}
		printf("%lld\n",ans);
	}
}
int main()
{
	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;
}