#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
#define MX 3005
//链式前向星存图
int n,m;
int edge0,head[MX];
struct way{
	int to,next;
	int val;
}edge[MX * 2];
void add_edge(int u,int v,int val)
{
	edge[++edge0].to = v;
	edge[edge0].val = val;
	edge[edge0].next = head[u];
	head[u] = edge0;
}

////Johnson求多源最短路 
int vis[MX];
//spfa初始化
int h[MX],times[MX];
bool spfa(int root)
{
	queue <int> que;
	memset(h,127,sizeof(h));
	h[root] = 0,vis[root] = 1;
	que.push(root);
	while (!que.empty())
	{
		int now = que.front();
		
		que.pop();
		vis[now] = 0;
		for (int eid = head[now];eid != 0;eid = edge[eid].next)
		{
			int to = edge[eid].to;
			if (h[now] + edge[eid].val < h[to])
			{
				h[to] = h[now] + edge[eid].val;
				if (vis[to] == 0)
				{
					vis[to] = 1;
					que.push(to); 
					times[to]++;
					if (times[to] == n + 1)
					{
						return 0;
					}
				}
			}
		}
	}
	return 1;
}
//dij
int dis[MX];
struct path{
	int now,dis;
	bool operator<(const path &another) const
	{
		return dis > another.dis;
	}
};
priority_queue <path> q;
void dij(int root)
{
	memset(vis,0,sizeof(vis));
	memset(dis,63,sizeof(dis));
	dis[root] = 0;
	q.push((path){root,0});
	while (!q.empty())
	{
		int now = q.top().now,d = q.top().dis;
		q.pop();
		if (vis[now] == 1)////有可能存在插队的情况 
		{
			continue;
		}
		vis[now] = 1;////比如 ： 更新为 8 进一次队列；更新为 5 进第二次队列;但 5 这次 先出队列，对外扩散后,之前的 8 已经没有意义了，来到时直接跳 
		for (int eid = head[now];eid != 0;eid = edge[eid].next)
		{
			int v = edge[eid].val,t = edge[eid].to;
			if (d + v < dis[t])
			{
				dis[t] = d + v;
				if (vis[t] == 0)
				{
					q.push((path){t,dis[t]});		
				}
			}
		}
	}
}

int main()
{
	scanf("%d %d",&n,&m);
	
	for (int i = 1;i <= m;i++)
	{
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		add_edge(u,v,w);
	}
	for (int i = 1;i <= n;i++)
	{
		add_edge(0,i,0);
	}
	
	if (!spfa(0))
	{
		printf("-1\n");
		return 0;
	}
	for (int i = 1;i <= n;i++)
	{
		for (int eid = head[i];eid != 0;eid = edge[eid].next)
		{
			edge[eid].val = edge[eid].val + h[i] - h[edge[eid].to];
		}
	}
	
	for (int i = 1;i <= n;i++)
	{
		long long ans = 0;
		dij(i);
		for (int j = 1;j <= n;j++)
		{
			if (dis[j] == 1061109567)
			{
				ans += (long long)j * 1e9;
			}
			else
			{
				ans += (long long)j * ((long long)dis[j] - (long long)(h[i] - h[j]));//还原 
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

超时求调，谢谢各位了