#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int,int> > Map[50005];

int n,m;
int D[50005];
bool InCoada[50005];

struct compara{
	bool operator() (int x, int y){
		return D[x] > D[y];
	}
};

//Dijkstra from start node to whatever node
//USING PRIORITY QUEUE 
void dijkstra(int nodStart){
	priority_queue<int, vector<int>, compara> Coada;
	for(int i=0; i<=n; i++){
		D[i]=99999999;
	}
	
	D[nodStart] = 0;
	Coada.push(nodStart);
	InCoada[nodStart] = true;
	while(!Coada.empty()){
		int nodCurent = Coada.top();
		Coada.pop();
		InCoada[nodCurent] = true;
		for(int i=0; i<Map[nodCurent].size(); i++){
			int Vecin  = Map[nodCurent][i].first;
			int Cost = Map[nodCurent][i].second;
			
			if(D[nodCurent] + Cost < D[Vecin]){
				D[Vecin] = D[nodCurent] + Cost;
				if(InCoada[Vecin]==false){
					Coada.push(Vecin);
					InCoada[Vecin] = true;
				}
			}
		}
	}
}

int main(int argc, char** argv) {	
	fin>>n>>m;
	
	int x, y, c;
	for(int i=0; i<m; i++){
		fin>>x>>y>>c;
		Map[x].push_back(make_pair(y,c));
	}
	
	dijkstra(1);
	
	for(int i=2; i<=n; i++){
		fout<<D[i]<<" ";
	}
	
	return 0;
}