RT

#include<bits/stdc++.h>
using namespace std;
int cs[30005],n;
long long zdl[30005],h[30005];
vector<int>lj[30005],bq[30005];
int a[30005],ddr,lsh[30005];
bool v[30005];
inline bool dnpx(int x,int y)
{
	return zdl[a[x]]>zdl[a[y]];
}
void push_up(int x)
{
	if(x==1)
	{
		return;
	}
	if(dnpx(x/2,x))
	{
		swap(a[x/2],a[x]);
		swap(lsh[a[x]],lsh[a[x/2]]);
		push_up(x/2);
	}
}
void push_down(int x)
{
	if(x*2>ddr)
	{
		return;
	}
	if(x*2+1>ddr)
	{
		if(dnpx(x,x*2))
		{
			swap(a[x*2],a[x]);
			swap(lsh[a[x]],lsh[a[x*2]]);
			push_down(x*2);
		}
		return;
	}
	if(dnpx(x*2,x*2+1))
	{
		if(dnpx(x,x*2+1))
		{
			swap(a[x],a[x*2+1]);
			swap(lsh[a[x]],lsh[a[x*2+1]]);
			push_down(x*2+1);
		}
	}else
	{
		if(dnpx(x,x*2))
		{
			swap(a[x*2],a[x]);
			swap(lsh[a[x]],lsh[a[x*2]]);
			push_down(x*2);
		}
	}
}
inline void fr(int x)
{
	ddr++;
	a[ddr]=x;
	lsh[x]=ddr;
	push_up(ddr);
}
inline void qc()
{
	lsh[a[1]]=0;
	a[1]=a[ddr];
	ddr--;
	push_down(1);
}
inline void xg(int x,int k)
{
	zdl[x]=k;
	push_up(lsh[x]);
}
inline void dij(int x)
{
	for(int i=0;i<3005;i++)
	{
		zdl[i]=1000000000;
		lsh[i]=0;
	}
	zdl[x]=0;
	ddr=0;
	fr(x);
	while(ddr>=1)
	{
		for(int i=0;i<lj[a[1]].size();i++)
		{
			if(zdl[lj[a[1]][i]]>zdl[a[1]]+bq[a[1]][i])
			{
				if(lsh[lj[a[1]][i]]==0)
				{
					zdl[lj[a[1]][i]]=zdl[a[1]]+bq[a[1]][i];
					fr(lj[a[1]][i]);
				}else
				{
					xg(lj[a[1]][i],zdl[a[1]]+bq[a[1]][i]);
				}
			}
		}
		qc();
	}
}
inline bool dead(int x)
{
	queue<int>q;
	for(int i=0;i<3005;i++)
	{
		h[i]=1000000000;
	}
	q.push(x);
	h[x]=0;
	v[x]=1;
	while(q.size())
	{
		for(int i=0;i<lj[q.front()].size();i++)
		{
			if(h[lj[q.front()][i]]>h[q.front()]+bq[q.front()][i])
			{
				h[lj[q.front()][i]]=h[q.front()]+bq[q.front()][i];
				if(!v[lj[q.front()][i]])
				{
					v[lj[q.front()][i]]=1;
					q.push(lj[q.front()][i]);
					cs[lj[q.front()][i]]++;
					if(cs[lj[q.front()][i]]==n+1)
					{
						return 1;
					}
				}
			}
		}
		v[q.front()]=0;
		q.pop();
	}
	return 0;
}
int main()
{
	int t;
	cin>>n>>t;
	while(t--)
	{
		int x,y,qwq;
		cin>>x>>y>>qwq;
		lj[x].push_back(y);
		bq[x].push_back(qwq);
	}
	for(int i=1;i<=n;i++)
	{
		lj[0].push_back(i);
		bq[0].push_back(0);
	}
	if(dead(0))
	{
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<lj[i].size();j++)
		{
			bq[i][j]+=h[i]-h[lj[i][j]];
		}
	}
	for(int i=1;i<=n;i++)
	{
		dij(i);
		long long ans=0;
		for(int j=1;j<=n;j++)
		{
			if(zdl[j]==1000000000)
			{
				ans+=1000000000*j;
			}else
			{
				ans+=(zdl[j]+h[j]-h[i])*j;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}