#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

class nodeDistPair{
	public : int node,dist;
	public : nodeDistPair(int n,int d){
		node=n;dist=d;
	}
	public : bool operator<(const nodeDistPair & other)const{return dist<other.dist;}
	public : bool operator>(const nodeDistPair & other)const{return dist>other.dist;}
};


int dist[50004];
vector< vector< pair<int,int> > > G(50004);

int main(){
	const int INF=50000006;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	priority_queue <nodeDistPair,vector<nodeDistPair>,greater<nodeDistPair> > pq;
	int n,m,x,y,c;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&x,&y,&c);//scanf("%d",&y);scanf("%d",&c);
		G[x].push_back(pair<int,int>(y,c));
	}
	for(int i=1;i<=n;i++){dist[i]=INF;}
	dist[1]=0;
	pq.push(nodeDistPair(1,0));
	int v;
	while(!pq.empty()){
		nodeDistPair u = pq.top();pq.pop();
		if(u.dist!=dist[u.node]) continue;
		for(int i=0;i<G[u.node].size();i++){
			v=G[u.node][i].first;
			if(dist[v]>dist[u.node]+G[u.node][i].second){
				//nodeDistPair newN(v,dist[u]+G[u][i].second);
				dist[v]=dist[u.node]+G[u.node][i].second;	
				//if(!inQueue[v])
					pq.push(nodeDistPair(v,dist[v]));
			}
		}
	}
	
	for(int i=2;i<=n;i++) printf("%d ",(dist[i]!=INF?dist[i]:0));
	return 0;
}