#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define int long long 
const int N=1e4+10,inf=1e9;
vector<pii> g[N];
int n,m,dis[N],a,b,c,ans;
int iq[N],num[N];
int vis[N];
inline void add(int x,int y,int z)
{
	g[x].push_back(make_pair(y,z));
}
inline bool spfa(int s)
{
	queue<int> q;
	for(int i=1;i<=n;++i)
		dis[i]=inf;
	iq[s]=1, q.push(s), dis[s]=0;
	while(!q.empty())
	{
		int u=q.front(); q.pop(); iq[u]=0;
		for(auto pl:g[u])
		{
			int wt=pl.second,v=pl.first;
			if(dis[v]>dis[u]+wt)
			{
				dis[v]=dis[u]+wt;
				if(!iq[v])
				{
					q.push(v), iq[v]=1, num[v]++;
					if(num[v]==n+1)
						return 0;
				}
			}
		}
	}
	return 1;
}
inline void dijkstra(int s)
{
	priority_queue<pii,vector<pii>,greater<pii> > q;
	for(int i=1;i<=n;++i)
		dis[i]=inf;
	q.push(make_pair(0,s)), dis[s]=0;
	while(!q.empty())
	{
		int u=q.top().second,dt=q.top().first; q.pop();
		for(auto pl:g[u])
		{
			int v=pl.first,wt=pl.second;
			if(dis[v]>dis[u]+wt)
				dis[v]=dis[u]+wt, q.push(make_pair(dis[v],v));
		}
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;++i)
		cin>>a>>b>>c, add(a,b,c);
	for(int i=1;i<=n;++i)
		add(0,i,0);
	if(!spfa(0))
		return cout<<-1, 0;
	for(int i=1;i<=n;++i)
		for(auto pl:g[i])
			pl.second+=dis[i]-dis[pl.first];
	for(int i=1;i<=n;++i)
	{
		dijkstra(i), ans=0;
		for(int j=1;j<=n;++j)
			ans+=dis[j]*j;
		cout<<ans<<endl;
	}
	return 0;
}