#include<bits/stdc++.h>
using namespace std;
const int MAXN=3007;
const int INF=1e9;
int Read();
void add_edge(int u,int v,int w);
struct Edge{
	int u,v,w,nxt;
}e[2*MAXN];int h[MAXN],e_cnt;
int n,m;
void minn_path();
void dijsktra(int k);
void add_virtual_spot_and_get_new_edge_weight();
void SPFA(int k);
void minus_circle();
int vis[MAXN],cnt[MAXN],dis[MAXN],re[MAXN];
int main(){
	n=Read(),m=Read();
	for(int i=1;i<=m;++i){
		int u=Read(),v=Read(),w=Read();
		add_edge(u,v,w);
	}
	add_virtual_spot_and_get_new_edge_weight();
	minn_path();
	return 0;
}
void minn_path(){
	for(int i=1;i<=n;++i){
		dijsktra(i);
		long long ans=0;
		for(int j=1;j<=n;++j)
			if(dis[j]==1e9)ans+=j*dis[j];
			else ans+=j*(dis[j]+re[j]-re[i]);
		printf("%lld\n",ans);
	}
}
void dijsktra(int k){
	for(int i=1;i<=n;++i)dis[i]=INF;
	memset(vis,0,sizeof(vis));
	dis[k]=0;
	priority_queue<pair<int,int> > q;
	q.push(make_pair(0,k));
	while(!q.empty()){
		int x=q.top().second;q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=h[x];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(dis[x]+w<dis[v]){
				dis[v]=dis[x]+w;
				q.push(make_pair(-dis[v],v));
			}
		}
	}
}
void add_virtual_spot_and_get_new_edge_weight(){
	for(int i=1;i<=n;++i){
		add_edge(0,i,0);
	}
	SPFA(0);
	for(int u=1;u<=n;++u)
		for(int i=h[u];i;i=e[i].nxt)
			e[i].w+=re[u]-re[e[i].v];
}
void SPFA(int k){
	memset(re,0x3f,sizeof(re));
	queue<int> q;
	vis[k]=1,re[k]=0,cnt[k]=1;
	q.push(k);
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=0;
		for(int i=h[x];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(re[x]+w<re[v]){
				re[v]=re[x]+w;
				if(!vis[v]){
					++cnt[v],vis[v]=1;q.push(v);
					if(cnt[v]==n+1){printf("-1\n");exit(0);}
				}
			}
		}
	}
}
void add_edge(int u,int v,int w){
	e[++e_cnt].u=u,e[e_cnt].v=v,e[e_cnt].w=w,e[e_cnt].nxt=h[u],h[u]=e_cnt;
}
int Read(){
	char ch=getchar();
	int f_r=1,res=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')f_r=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		res=res+res*4;
		res+=res+ch-'0';
		ch=getchar();
	}
	return f_r*res;
}