#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*b);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
#define num_l(a,v) POSL(a,v) //v未満の要素数
#define num_eql(a,v) POSU(a,v) //v以下の要素数
#define num_h(a,v) (a.size() - POSU(a,v)) //vより大きい要素数
#define num_eqh(a,v) (a.size() - POSL(a,v)) //v以上の要素数


class dijkstra{ 
//0indexed 
public: 
	int v,startv; 
	vector<int> d; 
	vector<vector<pair<int,int> > >e; 

	void initsize(int n0){ 
		d.resize(n0); 
		for(int i=0;i<n0;i++)d[i]=INT_MAX; 
		vector<pair<int,int> > ep; 
		for(int i=0;i<n0;i++)e.push_back(ep); 
		v=n0; 
	} 

	void initstart(int s){ 
		startv=s;
		for(int i=0;i<v;i++)d[i]=INT_MAX; 
		d[s]=0;
	}

	void make_edge(int x,int y,int cost){ 
		e[x].push_back(make_pair(y,cost)); 
		e[y].push_back(make_pair(x,cost)); 
	}

	void make_edgedir(int x,int y,int cost){ 
		e[x].push_back(make_pair(y,cost)); 
	}

	void calcdistance(){ 
		// <-cost,x>
		//cost startv->x
		priority_queue<pair<int,int> > q;
		pair<int,int> p;
		vector<bool> did;
		for(int i=0;i<v;i++)did.push_back(false); 
		did[startv]=true;
		for(int i=0;i<e[startv].size();i++){
			p.first=-e[startv][i].second;
			p.second=e[startv][i].first;
			q.push(p);
		}
		while(q.size()!=0){
			pair<int,int> p;
			p=q.top();
			q.pop();
			int x,costsx;
			x=p.second;
			costsx=-p.first;
			if(did[x]==true)continue;
			did[x]=true;
			d[x]=costsx;
			for(int i=0;i<e[x].size();i++){
				p.first=-(d[x]+e[x][i].second);
				p.second=e[x][i].first;
				if(did[p.second]==false)q.push(p);
			}
		}
	}
};

int main(){
	ll N,M;
	cin >> N >> M;
	vector< vector<pair<int,int>> > G(N);
	dijkstra di;
	di.initsize(N+1);//st ==> N

	FOR(i,0,M){
		int a,b,c;
		cin >> a >> b >> c;
		G[a-1].push_back({b-1,c});
		di.make_edgedir(a-1,b-1,c);
	}


	FOR(i,0,N){
		di.e[N] = G[i];
		di.initstart(N);
		di.calcdistance();
		int ans = di.d[i];
		if(ans == INT_MAX) ans = -1;
		cout << ans << endl;
	}	

}

#include<bits/stdc++.h>
#define M(x,y) make_pair(x,y)
#define ll long long
using namespace std;
struct node{
	int u,to,next,val;
};node e[4005];
int head[2005],dist[2005],vis[2005],dis[2005][2005],to[2005][2005],sum[2005],b[2005][2005];
int n,m,cnt=0,inf=999999999;
void add(int u,int v,int val){
	++cnt;
	e[cnt].u=u;
	e[cnt].to=v;
	e[cnt].val=val;
	to[v][++sum[v]]=u;
	e[cnt].next=head[u];
	head[u]=cnt;
	b[u][v]=min(b[u][v],val);
}
struct nd{
	int id,dis;
//	nd() {}
	nd(int _id, int _dis) : id(_id), dis(_dis) {}
	bool friend operator < (nd a,nd b){
		return a.dis<b.dis;
	}
}; 
priority_queue< pair<int,int> > q;
void dijstra(int s){
	for(int i=1;i<=n;i++) dis[s][i]=inf;
	memset(vis,0,sizeof(vis));
	dis[s][s]=0;
	q.push(M(0,s));
	while(!q.empty()){
        int u=q.top().second;
        q.pop(); 
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[s][v]>dis[s][u]+e[i].val){
                dis[s][v]=dis[s][u]+e[i].val;
                q.push(M(-dis[s][v],v));
            }
        }
    }
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			b[i][j]=inf;
		}
	}
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	for(int i=1;i<=n;i++){
		dijstra(i);
	}
	//cout<<"sss";
	/*for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<dis[i][j]<<" ";
		}
		cout<<endl;
	}*/
	for(int i=1;i<=n;i++){
		int ans=inf;
		for(int j=1;j<=sum[i];j++){
			if(dis[i][to[i][j]]!=inf){
				ans=min(ans,dis[i][to[i][j]]+b[to[i][j]][i]);
			}
		}
		if(ans!=inf){
			cout<<ans<<endl;
		}
		else{
			cout<<"-1"<<endl;
		}
	} 
} 