#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];
priority_queue<int, vector<int>, compara> Coada;
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){
	
	//Initializarea tuturor distantelor cu infinit etc etc
	for(int i=1; i<=n; i++){
		D[i]=2147483647;
	}
	
	D[nodStart] = 0;
	Coada.push(nodStart);
	InCoada[nodStart] = true;
	
	while(!Coada.empty()){
		
		int nodCurent = Coada.top();
		Coada.pop();
		InCoada[nodCurent] = true;
		for(size_t 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++)
    {
        if(D[i] != 2147483647)
            fout << D[i] << " ";
        else
            fout << "0 ";
    }
    
	return 0;
}