#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const int maxn=1e4+2;
int n,m;
ll dis[maxn];
ll ans[maxn][maxn];
bool viss[maxn];
queue <int> spfaq;
bool inq[maxn];int neg[maxn];
bool vis[maxn];
vector <pair <int,ll> > edge[maxn];
priority_queue <pair <ll,int> > q;
void qclear()
{
	priority_queue <pair <ll,int> > em;
	swap(em,q);
}
int spfa()
{
	for(int i=1;i<=n;i++) dis[i]=1e9;
	spfaq.push(0);dis[0]=0;
	
	inq[0]=1;
	while(!spfaq.empty())
	{
		int u=spfaq.front();
		spfaq.pop();
		inq[u]=0;
		for(int i=0;i<edge[u].size();i++)
		{
			int v=edge[u][i].first;
			if(dis[v]>dis[u]+edge[u][i].second)
			{
				dis[v]=dis[u]+edge[u][i].second;
				if(!inq[v])
				{
					inq[v]=1;
					spfaq.push(v);
					neg[v]++;
					if(neg[v]>n) return -1;
				}
			}
		}
	}
	return 1;
}
void dj(int st)
{
	qclear();
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++) ans[st][i]=1e9;
	q.push({0,st});
	ans[st][st]=0;
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<edge[u].size();i++)
		{
			int v=edge[u][i].first;
			if(ans[st][v]>ans[st][u]+edge[u][i].second)
			{
				ans[st][v]=ans[st][u]+edge[u][i].second;
				if(!vis[v]) q.push({ans[st][v],v});
			}
		}
	}
}
void work()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<edge[i].size();j++)
			edge[i][j].second+=(dis[i]-dis[edge[i][j].first]);

	}
}
void out()
{
	ll anss=0;
	for(int i=1;i<=n;i++)
	{
		anss=0;
		for(int j=1;j<=n;j++)
		{
//			cout<<ans[i][j]-dis[i]+dis[j]<<" ";
			if(ans[i][j]==1e9) anss+=j*1e9;
			else {
				anss+=j*(ans[i][j]-dis[i]+dis[j]);
			}
		}
		cout<<endl;
		printf("%lld\n",anss);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) edge[0].push_back({i,0});
	for(int i=1;i<=m;i++)
	{
		int u,v;ll w;
		scanf("%d%d%lld",&u,&v,&w);
		edge[u].push_back(make_pair(v,w));
	}
	if(spfa()==-1) {printf("-1");return 0;}
//	edge[0].clear();
	work();
	for(int i=1;i<=n;i++)
	{
		dj(i);
		ll anss=0;
		for(int j=1;j<=n;j++)
		{
			if(ans[i][j]==1e9) anss+=j*1e9;
			else anss+=j*(ans[i][j]+dis[j]-dis[i]);
		}
		cout<<anss<<endl;
	}
//	out();
	return 0;
}