#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
int he[3005],n,k,m,t[3005];
long long h[3005],ds[3005];
bool v[3005];
struct ys{
	int dis,to,nxt;
}aa[10005];
void add(int a,int b,int c){
	aa[++k].nxt=h[a];
	aa[k].dis=c;
	aa[k].to=b;
	he[a]=k;
	//cout<<a<<" "<<k<<endl;
}
bool spfa(int s){
	queue<int>q;
	memset(h,0x3f,sizeof(h));
	h[s]=0;v[s]=1;
	q.push(s);
	while(q.size()){
		int u=q.front();q.pop();
		v[u]=0;
		//cout<<he[u]<<endl;
		for(int i=he[u];i;i=aa[i].nxt){
			int vv=aa[i].to;
			if(h[vv]>h[u]+aa[i].dis){
				h[vv]=h[u]+aa[i].dis;
				if(!v[vv]){
					q.push(vv);
					v[vv]=1;
					t[vv]++;
					//cout<<vv<<" "<<t[vv]<<endl;
					if(t[vv]==n)return false;
				}
			}
		}
	}
	return true;
}
void dijkstra(int x){
	priority_queue<pair<int,int> >q;
	memset(v,0,sizeof(v));
	for(int i=1;i<=n;i++){
		ds[i]=INF;
	}
	ds[x]=0;
	q.push(make_pair(0,x));
	while(q.size()){
		int u=q.top().second;q.pop();
		if(v[u])continue;
		v[u]=1;
		for(int i=he[u];i;i=aa[i].nxt){
			int vv=aa[i].to;
			if(ds[vv]>ds[u]+aa[i].dis){
				ds[vv]=ds[u]+aa[i].dis;
				q.push(make_pair(-ds[vv],vv));
			}
		}
	}
	
}
int main(){
    ios::sync_with_stdio(false);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		//add(0,i,0);
	}
	for(int i=1;i<=n;i++)add(0,i,0);
	if(!spfa(0)){
		cout<<"-1"<<endl;
		return 0;
	}
	h[1]=0;
	for(int u=1;u<=n;u++){
		for(int i=he[u];i;i=aa[i].nxt){
		    //cout<<u<<" "<<aa[i].dis<<" ";
			aa[i].dis+=h[u]-h[aa[i].to];
			//cout<<h[u]<<" "<<h[aa[i].to]<<" "<<aa[i].dis<<endl;
		}
	}
	for(int i=1;i<=n;i++){
		dijkstra(i);
		long long ans=0;
		for(int j=1;j<=n;j++){
		    //cout<<i<<" "<<j<<" "<<ds[j]<<" ";
			if(ds[j]==INF){ans+=j*INF;continue;}
			//if(i==j)continue;
			ans+=j*(ds[j]+h[j]-h[i]);
			//cout<<ans<<endl;
		}
		//return 0;
		printf("%lld\n",ans);
	}
	return 0;
}