#include<bits/stdc++.h>
#define ll long long
#define INF 1000000000
using namespace std;
struct node{
  	int dis, id;
  	bool operator<(const node &a) const{
		return dis>a.dis;
	}
  	node(int d, int x){
  		dis=d,id=x;
	}
};
struct edge{
  int v,w,next;
}e[10001];
int head[5001],vis[5001],t[5001], cnt,n,m;
ll h[5001],dis[5001];
void add(int u,int v,int w){
	cnt++;
	e[cnt].v=v;
  	e[cnt].w=w;
  	e[cnt].next=head[u];
  	head[u]=cnt;
}
bool spfa(int s){
  	queue<int> q;
  	memset(h,63,sizeof h);
  	h[s]=0,vis[s]=1;
  	q.push(s);
  	while(!q.empty()){
    	int temp=q.front();
    	q.pop();
    	vis[temp]=0;
    	for(int i=head[temp];i; i=e[i].next){
      		int val=e[i].v;
      		if(h[val]>h[temp]+e[i].w){
        		h[val]=h[temp]+e[i].w;
        		if(!vis[val]){
          			vis[val]=1;
          			q.push(val);
          			t[val]++;
          			if(t[val]==n+1){
          				return 0;
					}
        		}
      		}
		}
  	}
  	return 1;
}
void dij(int s) {
  	priority_queue<node> q;
  	for(int i =1;i<=n;i++){
  		dis[i]=INF;
	}
  	memset(vis,0,sizeof vis);
  	dis[s]=0;
  	q.push(node(0,s));
  	while(!q.empty()){
    	int t=q.top().id;
    	q.pop();
    	if(vis[t]){
    		continue;
		}
    	vis[t]=1;
    	for(int i=head[t];i;i=e[i].next) {
      		int val=e[i].v;
      		if (dis[val]>dis[t]+e[i].w) {
        		dis[val]=dis[t]+e[i].w;
        		if(!vis[val]){
        			q.push((node){dis[val],val});
				}
      		}
    	}
  	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
  	for(int i=1;i<=n;i++){
  		add(0,i,0);
	}
  	if(!spfa(0)) {
    	printf("-1");
    	exit(0);
  	}
  	for(int i=1;i<=n;i++){
  		for(int j=head[i];j;j=e[j].next){
    		e[j].w+=h[i]-h[e[j].v];
		}
	}
  	for(int i=1;i<=n;i++){
    	dij(i);
    	ll ans=0;
    	for(int j=1;j<=n;j++){
      		if(dis[j]==INF){
      			ans+=j*INF;
			}
    		else{
				ans+=j*(dis[j]+h[j]-h[i]);
			}    
    	}
		printf("%lld\n",ans);
	}
  	return 0;
}