#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e9;
int n,m;
struct node
{
	int nxt,to,w;
}e[10005];
int head[10005],cntt;
void add(int from,int to,int w)
{
	cntt++;
	e[cntt].to=to;
	e[cntt].w=w;
	e[cntt].nxt=head[from];
	head[from]=cntt;
}
int vis[3005];
queue <int> q;
bool flag=0;
int d[3005];
int sum,num;
int cnt[3005];
void spfa()
{
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[0]=0;
	vis[0]=1;
	q.push(0);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			int w=e[i].w;
			if(d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				if(!vis[v])
				{
					q.push(v);
					cnt[v]++;
					if(cnt[v]>n)
					{
						flag=1;
						return ;
					}
					vis[v]=1;
				}
			}
		}
	}
	return ;
}
void dfs(int u)
{
	vis[u]=1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		int w=e[i].w;
		e[i].w=w+d[u]-d[v];
		if(vis[v]==0) dfs(v);
	}
	return ;
}
int dis[3005];
priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qq;
void dij(int s)
{
	for(int i=1;i<=n;i++) dis[i]=inf;
	dis[s]=0;
	qq.push(make_pair(0,s));
	while(!qq.empty())
	{
		int u=qq.top().second;
		qq.pop();
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			int w=e[i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				qq.push(make_pair(dis[v],v));
			}
		}
	}
	return ;
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	for(int i=1;i<=n;i++) add(0,i,0);
	spfa();
	if(flag==1)
	{
		cout<<"-1";
		return 0;
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		if(vis[i]==0)
			dfs(i);
	for(int i=1;i<=n;i++)
	{
		dij(i);
		int qwq=0;
		for(int j=1;j<=n;j++)
		{
			if(dis[j]==inf) qwq+=j*inf;
			else qwq+=(dis[j]-d[i]+d[j])*j;
		}
		cout<<qwq<<'\n';
	}
	return 0;
}