#include<bits/stdc++.h>
using namespace std;
long long dis[3300][3300];
inline int read()
{
	int x=0;bool f=0;char c=getchar();
	for(;!isdigit(c);f=(c=='-'),c=getchar());
	for(;isdigit(c);x=(x<<3)+(x<<1)+c-48,c=getchar());
	return f?-x:x;
}
inline void write(long long x)
{
	if(x==0)putchar('0');
	if(x<0)putchar('-'),x=-x;
	int temp[20],top=0;
	for(;x;temp[top++]=x%10+48,x/=10);
	for(;top;putchar(temp[--top]));
	putchar('\n');
}
int main()
{
	int n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=1e18;
	int u,v,w;
	for(int i=1;i<=m;i++)
	{
		u=read(),v=read(),w=read();
		dis[u][v]=min(dis[u][v],(long long)w);
	}
	for(int i=1;i<=n;i++)
		dis[i][i]=0;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
				if(dis[i][j]+dis[j][i]<0)
				{
					write(-1);
					return 0;
				}
			}
	long long result;
	for(int i=1;i<=n;i++)
	{
		result=0;
		for(int j=1;j<=n;j++)
			result+=j*min(dis[i][j],(long long)1e9);
		write(result);
	}
	return 0;
}

用Floyd过了负环的点，难道Floyd是能检测负环的？求反例