#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack> 
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int N=5000,M=7000;
const int INF=1e911;
int n,m,tot;
int ver[M],nex[M],edge[M],head[N],cnt[N];
ll d1[N],d[N];
bool v[N];
queue<int> q1;
priority_queue< pp,vector<pp>,greater<pp> > q;
void add(ll x,ll y,ll z)
{
	ver[++tot]=y;
	edge[tot]=z;
	nex[tot]=head[x];
	head[x]=tot;
}
bool spfa(int s)
{
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++) d1[i]=INF;
	memset(v,0,sizeof(v));
	d1[s]=0,v[s]=1,cnt[s]=1;
	q1.push(s);
	while(!q1.empty())
	{
		ll x=q1.front();
		q1.pop();
		v[x]=0;
		for(int i=head[x];i;i=nex[i])
		{
			ll y=ver[i],z=edge[i];
			if(d1[y]>d1[x]+z)
			{
				d1[y]=d1[x]+z;
				cnt[y]=cnt[x]+1;
				if(cnt[y]>n) return false;
				if(!v[y]) 
				{
					q1.push(y);
					v[y]=1;
				}
			}
		}
	}
	return true;
}
void dijkstra(int s)
{
	for(int i=1;i<=n;i++) d[i]=INF;
	memset(v,0,sizeof(v));
	d[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(v[x]) continue;
		v[x]=1;
	    for(int i=head[x];i;i=nex[i])
	    {
	    	ll y=ver[i],z=edge[i];
	    	if(d[y]>d[x]+z)
	    	{
	    		d[y]=d[x]+z;
	    		q.push(make_pair(d[y],y));
			}
		}
	}
}
void johnson()
{
	for(int j=1;j<=n;j++)
		for(int i=head[j];i;i=nex[i])
			edge[i]+=d1[j]-d1[ver[i]];
	for(int i=1;i<=n;i++)
	{
		dijkstra(i);
		ll ans=0;
		for(int j=1;j<=n;j++)
		{
			if(d[j]==INF) ans+=j*INF;
			else ans+=j*(d[j]+d1[j]-d1[i]);
		}
		cout<<ans<<endl;
	}	
}
int main()
{
	cin>>n>>m;
	while(m--)
	{
		ll u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int i=1;i<=n;++i) add(0,i,0);
	if(!spfa(0)) cout<<"-1"<<endl;
	else johnson();
	return 0;
}