求助，玄关

//#include<all_include.h>
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<limits.h>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<array>
#include<list>
#include<map>
#include<set>
#define umap unordered_map
#define int long long
#define MAXN 1145141
#define MAXX (1<<30)
#define endl '\n'
using namespace std;
struct Edge{
	int next,to,val;
}edge[MAXN];
int n,m,u,v,t,ans;
int shortest[MAXN];
int cnt[MAXN];
template<typename T>
inline void read(T &x){
	int sign=1;x=0;char c=getchar();
	while(!isdigit(c)){if(c=='-')sign=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=sign;
}//getchar_unlocked()
template<typename T1,typename ...T2>
inline void read(T1 &tmp,T2 &...tmps){read(tmp);read(tmps...);}
int head[MAXN],sum;
void add(int from,int to,int val){
	edge[++sum].next=head[from];
	edge[sum].val=val;
	edge[sum].to=to;
	head[from]=sum;
}
bool vis[MAXN];
bool dis[MAXN];
void memset_(){
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++) dis[i]=1e9;
}
bool spfa(){
	queue<int> que;
	for(int i=1;i<=n;i++) que.push(i),vis[i]=true;
	while(!que.empty()){
		int x=que.front();
		que.pop();
		vis[x]=false;
		for(int i=head[x];i;i=edge[i].next){
			int to=edge[i].to;
			int val=edge[i].val;
			if(shortest[to]>shortest[x]+val){
				shortest[to]=shortest[x]+val;
				cnt[to]++;
				if(cnt[to]>=n+1){
					return true;
				}
				if(!vis[to]){
					vis[to]=true;
					que.push(to);
				}
			}
		}
	}
	return false;
}
void dijkstra(int s){
	memset_();
	priority_queue<pair<int,int> > que;
	que.push(make_pair(0,s));
	vis[s]=true;dis[s]=0;
	while(!que.empty()){
		int x=que.top().second;
		que.pop();
		for(int i=head[x];i;i=edge[i].next){
			int to=edge[i].to;
			int val=edge[i].val;
			if(dis[to]>dis[x]+val){
				dis[to]=dis[x]+val;
				if(!vis[to]){
					vis[to]=true;
					que.push(make_pair(-dis[to],to));
				}
			}
		}
	}
}
signed main(){
	read(n,m);
	for(int i=1;i<=m;i++){
		read(u,v,t);
		add(u,v,t);
	}
	for(int i=1;i<=n;i++){
		add(0,i,0);
	}
	if(spfa()){
		cout<<-1<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=edge[j].next){
			int to=edge[j].to;
			edge[j].val+=shortest[i]-shortest[to];
		}
	}
	for(int i=1;i<=n;i++){
		dijkstra(i);
		ans=0;
		for(int j=1;j<=n;j++){
			if(dis[j]==1e9){
				ans+=j*1e9;
			}else{
				ans+=j*(dis[j]+shortest[j]-shortest[i]);
			}
		}
		cout<<ans<<endl;
	}
  	return 0;
}