#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

#define INF 1e9
#define ll long long

using namespace std;

struct node1
{
	ll x , d;
	
	bool operator < (const node1 b) const
	{
		return d > b.d;
	}
};

struct node2
{
	ll v , w;
};

ll n , m , dis[30005] , h[30005] , cnt[30005] , vis[30005] , ans;
vector <node2> link[30005];

void add (ll u , ll v , ll w)
{
	link[u].push_back(node2{v,w});
	return;
}

void init()
{
	ll u , v , w;
	scanf("%lld%lld" , &n , &m); //node2 , add
	
	for (ll i = 1 ; i <= m ; i++)
	{
		scanf("%lld%lld%lld" , &u , &v , &w);
		add(u , v , w);
	}
	
	return;
}

bool SPFA(ll s)
{
	
	queue <ll> q;
	
	//init
	memset (h , 0x3f , sizeof(h));
	
	h[s] = 0 , vis[s] = 1;
	q.push(s);
	
	ll u;
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		vis[u] = 0;
		
		for (auto i : link[u])
		{
			if (h[i.v] > h[u]+i.w)
			{
				h[i.v] = h[u]+i.w;
				
				if (!vis[i.v])
				{ 
					q.push(i.v);
					vis[i.v] = 1;
					
					if (++cnt[i.v] > n) return true;
				}
			}
		}
	}
	
	return false;
}

void clear()
{
	for (ll i = 1 ; i <= n ; i++) dis[i] = INF;
	return;
}

void dijkstra(ll s)
{
	clear();
	priority_queue <node1> q;
	node1 u;
	
	q.push(node1{s , 0});
	dis[s] = 0;
	
	while (!q.empty())
	{
		u = q.top();
		q.pop();
		
		if (dis[u.x] != INF) continue; 
			
		dis[u.x] = u.d;
		
		for (auto i : link[u.x])
			q.push(node1{i.v , u.d+i.w});
	}
	
	return;
}

int main()
{
	init();
	
	for (int i = 1 ; i <= n ; i++) add(0,i,0);
	if (SPFA(0)) {printf("-1"); return 0;}
	
	for (ll u = 1 ; u <= n ; u++)
		for (auto link : link[u])
			link.w += h[u] - h[link.v];
	
	for (ll i = 1 ; i <= n ; i++)
	{
		dijkstra(i);
		ans = 0;
		
		for (ll j = 1 ; j <= n ; j++)
			if (dis[j] == INF)
				ans += j*INF;
			else
				ans += j * (dis[j] + h[j] - h[i]);
		
		
		printf("%lld\n" , ans);
	}
	
	return 0;
}