#include<iostream>
#include<vector>
#include<queue>
#define int long long
using namespace std;
struct node
{
	int pos,v;
	node(int a,int b):pos(a),v(b){}
};
struct cmp
{
	bool operator() (const node& a,const node& b){return a.v>b.v;}
};
vector<vector<node> > mp;
deque<int> q;
vector<int> ifdist;
vector<int> dist;
vector<int> h;
priority_queue<node,vector<node>,cmp> pq;
long long sum=0;
int n,m;
main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;
	mp.resize(n+1);
	ifdist.resize(n+1,0);
	dist.resize(n+1,(int)1e9);
	h.resize(n+1,(int)1e9);
	for(int i=1;i<=n;i++)
	{
		mp[0].emplace_back(node(i,0));
	}
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		mp[a].emplace_back(node(b,c));
	}
	q.push_back(0);
	ifdist[0]++;
	h[0]=0;
	//spfa
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(vector<node>::iterator it=mp[x].begin();it!=mp[x].end();it++)
		{
			if(h[x]+it->v<h[it->pos])
			{
				h[it->pos]=h[x]+it->v;
				ifdist[it->pos]++;
				if(ifdist[it->pos]>=n)
				{
					cout<<-1;
					return 0;
				}
				if(!q.empty()&&h[it->pos]<h[q.front()])//SLF
				q.push_front(it->pos);
				else
				q.push_back(it->pos);
			}
		}
	}
	//w(u,v)->w(u,v)+dist[u]-dist[v]
	for(int i=1;i<=n;i++)
		for(vector<node>::iterator it=mp[i].begin();it!=mp[i].end();it++)
			it->v=it->v+h[i]-h[it->pos];
	//n遍dij
	for(int kkk=1;kkk<=n;kkk++)
	{
		sum=0;
		dist.assign(n+1,(int)1e9);
		ifdist.assign(n+1,0);
		dist[kkk]=0;
		ifdist[kkk]=1;
		pq.push(node(kkk,0));
		while(!pq.empty())
		{
			int x=pq.top().pos;pq.pop();
			for(vector<node>::iterator it=mp[x].begin();it!=mp[x].end();it++)
			{
				if(dist[x]+it->v<dist[it->pos])
				{
				dist[it->pos]=dist[x]+it->v;
				pq.push(node(it->pos,dist[it->pos]));
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(dist[i]==(int)1e9) sum+=i*(int)1e9;
			else sum +=i*(dist[i]+h[i]-h[kkk]);
		}
		cout<<sum<<"\n";
	} 
}

#8TLE 求调