#include <bits/stdc++.h>
#define inf 1000000000
#define cst first
#define nod second

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector < pair<int,int> > mv[50005];
int viz[50005],cost[50005];
priority_queue < pair<int,int>, vector <pair<int,int> >, greater < pair<int,int> > > q;

void Dijkstra(){
	int i;
	pair <int,int> first;

	cost[1]=0;
	q.push(make_pair(0,1));

	while(!q.empty()){
		first=q.top();
		int vec=first.nod;
		q.pop();

		if(viz[vec]==1)
			continue;
		viz[vec]=1;

		for(i=0;i<mv[vec].size();i++){
			if(cost[mv[vec][i].nod]>cost[vec]+mv[vec][i].cst){
				cost[mv[vec][i].nod]=cost[vec]+mv[vec][i].cst;
				q.push(make_pair(cost[mv[vec][i].nod],mv[vec][i].nod));
			}
		}
	}
}

int main(){
	int n,m,i,x,y,c;

	fin>>n>>m;

	for(i=1;i<=n;i++)
		cost[i]=inf;

	for(i=1;i<=m;i++){
		fin>>x>>y>>c;
		mv[x].push_back(make_pair(c,y));
	}

	Dijkstra();

	for(i=2;i<=n;i++)
		if(cost[i]==inf)
			fout<<0<<" ";
		else fout<<cost[i]<<" ";

	return 0;
}