#include<bits/stdc++.h>
using namespace std;
const int N=6666,M=N<<1,inf=1000000000;
struct lsqxx{
	int nxt,to;
	long long w;
}e[M];
int n,m,t,h[N],c[N];
long long s,a[N],d[N];
bool b[N];
void Add_Edge(int x,int y,int z){
	e[++t]=(lsqxx){h[x],y,z};
	h[x]=t;
}
void SPFA(int s){
	int x,y;
	long long z;
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)a[i]=inf;
	a[s]=0;
	b[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		x=q.front();
		q.pop();
		b[x]=0;
		for(int i=h[x];~i;i=e[i].nxt){
			y=e[i].to;
			z=e[i].w;
			if(a[y]>a[x]+z){
				a[y]=a[x]+z;
				if(!b[y]){
					b[y]=1;
					q.push(y);
					c[y]++;
					if(c[y]==n){
						cout<<-1<<endl;
						exit(0);
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=h[i];~j;j=e[j].nxt)
			e[j].w=e[j].w+a[i]-a[e[j].to];
}
long long Dijkstra(int s){
	int x,y;
	long long z;
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)d[i]=inf;
	d[s]=0;
	priority_queue<pair<int,int> >q;
	q.push(make_pair(0,s));
	while(!q.empty()){
		x=q.top().second;
		q.pop();
		if(b[x])continue;
		b[x]=1;
		for(int i=h[x];~i;i=e[i].nxt){
			y=e[i].to;
			z=e[i].w;
			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				q.push(make_pair(-d[y],y));
			}
		}
	}
	z=0;
	for(int i=1;i<=n;i++)z+=d[i]==inf?d[i]*i:(d[i]+a[i]-a[s])*i;
	return z;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(h,255,sizeof(h));
	int x,y;
	long long z;
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>x>>y>>z,Add_Edge(x,y,z);
	for(int i=1;i<=n;i++)Add_Edge(0,i,0);
	SPFA(0);
	for(int i=1;i<=n;i++)cout<<Dijkstra(i)<<endl;
	return 0;
}

RT，最后一个点死活过不去……

各位大佬求调QwQ