#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
const vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T>void debag(const vector<T> &a){cerr<<"debag :";for(auto v:a)cerr<<v<<" ";cerr<<"\n";}
template<class T>void print(const vector<T> &a){for(auto v:a)cout<<v<<" ";cout<<"\n";}
struct edge{
    ll to,cost;
    edge(ll to,ll cost):to(to),cost(cost) {}
};
vector<vector<edge>> g;
vector<ll> d;
int n,m;
ll ds(ll s){
    d.resize(n);
    for(int i=0;i<n;i++)d[i]=inf;
    d[s]=0;
    priority_queue<P,vector<P>,greater<P>> q;
    q.push(P(0,s));//始点を０で置く
    ll res=inf;
    while(!q.empty()){
        ll cur=q.top().se,val=q.top().fi;
        q.pop();
        if(val>d[cur])continue;
        for(edge &e:g[cur]){
            if(e.to==s){
                 chmin(res,val+e.cost);
                 continue;
            }
            if(d[e.to]>d[cur]+e.cost){
                d[e.to]=d[cur]+e.cost;
                q.push(P(d[e.to],e.to));
            }
        }
    }
    return res;
}
int main(){
    cin>>n>>m;
    g.resize(n);
    for(int i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        --a;--b;
        g[a].emplace_back(b,c);
    }
    for(int i=0;i<n;i++){
          ll ans=ds(i);
          cout<<(ans>=inf?-1:ans)<<"\n";
    }

}
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>

#define int long long
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
#define lc (x<<1)
#define rc (x<<1|1)
#define fan(x) (((x-1)^1)+1)
#define max Max
#define min Min
#define abs Abs

using namespace std;

inline int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=(ans<<1)+(ans<<3)+c-'0';c=getchar();}
	return ans*f;
}

inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x/10) write(x/10);
	putchar((char)(x%10)+'0');
}

template<typename T>inline T Abs(T a){return a>0?a:-a;};
template<typename T,typename TT>inline T Min(T a,TT b){return a>b?b:a;}
template<typename T,typename TT> inline T Max(T a,TT b){return a>b?a:b;}

const int N=2005;
int n,m,vis[N],dis[N][N],mp[N][N],ans;

struct Edge
{
	int v,w,ne;
}e[N*2];
int head[N],tot;

struct Node
{
	int u,w;
	bool operator < (const Node &x)const
	{
		return w>x.w;
	}
};

inline void add(int u,int v,int w);
inline void dij(int st);

signed main()
{
	n=read();m=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		if(mp[u][v]==0) mp[u][v]=w;
		else mp[u][v]=min(mp[u][v],w);
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(i!=j&&mp[i][j]!=0) add(i,j,mp[i][j]);
	for(int i=1;i<=n;++i) dij(i);
	for(int i=1;i<=n;++i)
	{
		int ans=1e18;
		for(int j=1;j<=n;++j)
			if(i==j)
			{
				if(dis[i][j]!=-1)
					ans=min(ans,dis[i][j]);
			}
			else if(dis[i][j]!=-1&&dis[j][i]!=-1)
				ans=min(ans,dis[i][j]+dis[j][i]);
		if(ans==1e18) printf("-1\n");
		else printf("%lld\n",ans);
	}
	return 0;
}

inline void add(int u,int v,int w)
{
	e[++tot]=(Edge){v,w,head[u]};
	head[u]=tot;
}

inline void dij(int st)
{
	memset(vis,0,sizeof(vis));
	memset(dis[st],-1,sizeof(dis[st]));
	priority_queue<Node> qu;
	qu.push((Node){st,0});
	dis[st][st]=0;
	while(!qu.empty())
	{
		int u=qu.top().u;
		qu.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].ne)
		{
			int v=e[i].v;
			if(dis[st][v]==-1||dis[st][v]>dis[st][u]+e[i].w)
			{
				dis[st][v]=dis[st][u]+e[i].w;
				if(!vis[v]) qu.push((Node){v,dis[st][v]});
			}
		}
	}
	if(mp[st][st]!=0) dis[st][st]=mp[st][st];
	else dis[st][st]=-1;
}