#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

long long n, m;
struct Edge
{
	long long to, w, next;
}edge[6005];
long long head[3005];
long long cnt;
void addEdge(long long u, long long v, long long w)
{
	cnt++;
	edge[cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
long long dis0[3005];
bool SPFAJohnson()
{
	for(int i = 1; i <= n; i++)
	{
		addEdge(0, i, 0);
	}
	long long step[3005];
	bool inQ[3005];
	for(long long i = 0; i <= n; i++)
	{
		dis0[i] = 1000000000;
		step[i] = 0;
		inQ[i] = 0;
	}
	queue <long long> q;
	dis0[0] = 0;
	q.push(0);
	inQ[0] = 1;
	while(!q.empty())
	{
		long long tem = q.front();
		q.pop();
		inQ[tem] = 0;
		for(long long i = head[tem]; i; i = edge[i].next)
		{
			if(dis0[edge[i].to] > dis0[tem] + edge[i].w)
			{
				dis0[edge[i].to] = dis0[tem] + edge[i].w;
				if(!inQ[edge[i].to])
				{
					q.push(edge[i].to);
					inQ[edge[i].to] = 1;
					step[edge[i].to]++;
					if(step[edge[i].to] > n)
					{
						return 0;
					}
				}
			}
		}
	}
	for(long long i = 1; i <= n; i++)
	{
		for(long long j = head[i]; j; j = edge[j].next)
		{
			edge[j].w = edge[j].w + dis0[i] - dis0[edge[j].to];
		}
	}
	return 1;
}
struct Node
{
	long long ind;
	long long dis;
	bool operator < (const Node &x) const
	{
		return x.dis < dis;
	}
};
long long Dijkstra(long long s)
{
	long long ans = 0;
	long long dis[3005];
	bool vis[3005];
	priority_queue <Node> q;
	for(long long i = 1; i <= n; i++)
	{
		dis[i] = 1000000000;
		vis[i] = 0;
	}
	dis[s] = 0;
	q.push((Node){s, 0});
	while(!q.empty())
	{
		Node tem = q.top();
		q.pop();
		if(vis[tem.ind])
		{
			continue;
		}
		vis[tem.ind] = 1;
		for(long long i = head[tem.ind]; i; i = edge[i].next)
		{
			if(dis[edge[i].to] > dis[tem.ind] + edge[i].w)
			{
				dis[edge[i].to] = dis[tem.ind] + edge[i].w;
				if(!vis[edge[i].to])
				{
					q.push((Node){edge[i].to, dis[edge[i].to]});
				}
			}
		}
	}
	for(long long i = 1; i <= n; i++)
	{
		if(dis[i] == 1000000000)
		{
			ans += i * 1000000000;
		}
		else if(i != s)
		{
			ans += i * (dis[i] - dis0[s] + dis0[i]);
		}
	}
	return ans;
}
int main()
{
	scanf("%lld %lld", &n, &m);
	for(long long i = 1; i <= m; i++)
	{
		long long u, v, w;
		scanf("%lld %lld %lld", &u, &v, &w);
		addEdge(u, v, w);
	}
	if(!SPFAJohnson())
	{
		printf("-1");
		return 0;
	}
	for(long long i = 1; i <= n; i++)
	{
		printf("%lld\n", Dijkstra(i));
	}
	return 0;
}

WA on #8, #9, #11.