#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define endl '\n'
#define itn int
#define pi pair<int,int>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
const int MOD1=1e9+7;
const int MOD2=998244353;
const int N=3e3+5;
const int M=9e3+5;
struct Edge{
	int nxt,to,val;
}edge[M];
int n,m,cnt,head[N],dis[N],_cnt[N];
ll ans;
bool vis[N];
stack<int> p;
queue<int> q;
priority_queue<pi,vector<pi >,greater<pi > > pq;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' or ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
template<typename T>
inline void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void add(int u,itn v,itn w){
	edge[++cnt]=(Edge){head[u],v,w};
	head[u]=cnt;
}
inline void SPFA_A(){
	fill(dis+1,dis+n+1,1e9);
	p.push(0);
	vis[0]=1;
	dis[0]=0;
	while(!p.empty()){
		int u=p.top();
		p.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			int w=edge[i].val;
			if(w+dis[u]<dis[v]){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					p.push(v);
					vis[v]=1;
					if(++_cnt[v]>n){
						cout<<-1;
						exit(0);
					}
				}
			}
		}
	}
}
inline void SPFA_B(int s){
	fill(dis+1,dis+n+1,1e9);
	fill(vis+1,vis+n+1,0);
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			int w=edge[i].val;
			if(w+dis[u]<dis[v]){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
inline void SPFA_C(int s){
	fill(dis+1,dis+n+1,1e9);
	//fill(vis+1,vis+n+1,0);
	pq.push(make_pair(0,s));
	vis[s]=1;
	dis[s]=0;
	while(!pq.empty()){
		int u=pq.top().second;
		pq.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			int w=edge[i].val;
			if(w+dis[u]<dis[v]){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					pq.push(make_pair(dis[v],v));
					vis[v]=1;
				}
			}
		}
	}
}
inline void Solve(){
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		int u,v,w;
		u=read();
		v=read();
		w=read();
		add(u,v,w); 
	}
	for(int i=1;i<=n;i++)
		add(0,i,0);
	SPFA_A();
	for(int i=1;i<=n;i++){
		SPFA_C(i);
		ans=0;
		for(int j=1;j<=n;j++)
			ans+=(ll)j*(ll)dis[j];
		write(ans);
		putchar('\n');
	}
}
int main()
{
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int T=1;
    //cin>>T;
    while(T--)
    	Solve();
    return 0;
}