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

//struct nodeDistPair{
//	int node,dist;
//	nodeDistPair(int n,int d){
//		node=n;dist=d;
//	}
//};


//bool operator<(nodeDistPair n1,nodeDistPair n2){return n1.dist<n2.dist;}
//bool operator>(nodeDistPair n1,nodeDistPair n2){return n1.dist>n2.dist;}
int dist[50004];
vector< vector< pair<int,int> > > G(50004);
//vector< vector<int> > C(50004);

class cmp{
	public: bool operator()(const int& i,const int& j) const{return dist[i]>dist[j];}
};

int main(){
	const int INF=50000006;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	priority_queue <int,vector<int>,cmp > 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(1);
	int v;
	while(!pq.empty()){
		int u = pq.top();pq.pop();
		for(int i=0;i<G[u].size();i++){
			v=G[u][i].first;
			if(dist[v]>dist[u]+G[u][i].second){
				//nodeDistPair newN(v,dist[u]+G[u][i].second);
				dist[v]=dist[u]+G[u][i].second;	
				//if(!inQueue[v])
					pq.push(v);
			}
		}
	}
	
	for(int i=2;i<=n;i++) printf("%d ",(dist[i]!=INF?dist[i]:0));
	return 0;
}