#include<bits/stdc++.h>
typedef long long ll;
const ll maxn=10005,inf=1e9;
ll head[maxn],ver[maxn],nxt[maxn],wei[maxn];
ll d[maxn];
ll n,m,tot;
ll h[maxn];
bool v[maxn];
ll t[maxn];
void add(int x,int y,int z){
	nxt[++tot]=head[x];
	head[x]=tot;
	ver[tot]=y;
	wei[tot]=z;
}
int spfa(int x){
	std::deque<int>q;
	memset(v,0,sizeof(v));
	for(int i=1;i<=n;i++){
		h[i]=inf;
	}
	h[x]=0;
	q.push_back(x);
	int sum=h[x];
	int num=1;
	t[x]++;
	v[x]=1;
	while(!q.empty()){
		int x=q.front();
		while(h[x]*num>sum){
			q.pop_front();
			q.push_back(x);
			x=q.front();
		}
		q.pop_front();
		sum-=h[x];
		num--;
		v[x]=0;
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			int z=wei[i];
			if(h[y]>h[x]+z){
				h[y]=h[x]+z;
				if(!v[y]){
					if(!q.empty()&&h[y]>h[q.front()]){
						q.push_back(y);
					}
					else{
						q.push_front(y);
					}
					sum+=h[y];
					num++;
					t[y]++;
					if(t[y]>=n){
						return 1;
					}
					v[y]=1;
				}
			}
		}
	}
	return 0;
}
void dijkstra(int x){
	std::priority_queue<std::pair<int,int> >q;
	for(int i=1;i<=n;i++){
		d[i]=inf;
	}
	std::memset(v,0,sizeof(v));
	d[x]=0;
	q.push(std::make_pair(0,x));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(v[x])continue;
		v[x]=1;
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i],z=wei[i];
			if(v[y])continue;
			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				if(!v[y])q.push(std::make_pair(-d[y],y));
			}
		}
	}
}
int main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		std::cin>>x>>y>>z;
		add(x,y,z);
	}
	for(int i=1;i<=n;i++){
		add(0,i,0);
	}
	if(spfa(0)){
		std::cout<<"-1\n";
		return 0;
	}
	for(int x=1;x<=n;x++){
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			wei[i]+=h[x]-h[y];
		}
	}
	for(int i=1;i<=n;i++){
		dijkstra(i);
		ll ans=0;
		for(int j=1;j<=n;j++){
			if(d[j]==inf)ans+=j*inf;
			else ans+=j*(d[j]-h[i]+h[j]);
		}
		std::cout<<ans<<"\n";
	}
}