#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define NMax 50002
#define INF 666666

using namespace std;


vector< pair<int,int> > Graf[NMax];
int cost[NMax];
int viz[NMax];

struct cmp {
	
	bool operator()(const int &a,const int &b) const {

		return cost[a]>cost[b];

	}
};
priority_queue<int, vector<int>, cmp> Q;

int n,m;

void cit();
void rez();
void afis();


int main() {
	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	cit();
	rez();
	afis();
	
	return 0;
}

void cit() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m;i++) {
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		Graf[x].push_back(make_pair(y,z));
	}
}


void rez() {
	
	vector< pair<int,int> >::iterator it;
	int i;
	
	
	for(i=2; i<=n;i++)
		cost[i]=INF;
	
	Q.push(1);
	
	while(!Q.empty()) {
		
		int min=Q.top();
		Q.pop();
		
		viz[min]=0;
		
		for(it=Graf[min].begin(); it!=Graf[min].end(); it++) {
			
			if( cost[it->first]>cost[min]+it->second ) {
				
				cost[it->first]=cost[min]+it->second;
				
				if(!viz[it->first]) {
					Q.push(it->first);
					viz[it->first]=1;
				}
			}
			
		}
		
	}

}


void afis() {
	for(int i=2; i<=n;i++)
		printf("%d ",cost[i]==INF?0:cost[i]);
}