#include <fstream>
#include <vector>
#include <map>
#include <utility>
#include <queue>

using namespace std;

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

const int INF=1<<30;

map <int,vector<pair <int,int> > > graph;
map <int,int> dist;
map <int,bool> visited;
int vertices,edges;

void read(){
	in>>vertices;
	in>>edges;
	int x,y,c;
	for(int i=1;i<=edges;++i){
		in>>x>>y>>c;
		graph[x].push_back(make_pair(y,c));
	}
}

void Dijkstra(){
	int i;
	priority_queue< pair<int,int> > heap; // insert in the queue the distances with minus 
	for(int i=2;i<=vertices;++i){
		dist[i]=INF;
		visited[i]=false;
	}
	dist[1]=0;
	visited[1]=true;
	vector<pair <int,int> > ::iterator it;
	pair <int,int> currentpair;
	for(it=graph[1].begin();it!=graph[1].end();++it){
		currentpair=*it;
		heap.push(make_pair(-(currentpair.second),currentpair.first));
	}
	int unvisited=vertices-1,currentnode,currentdistance;
	while(unvisited){
		while(visited[heap.top().second]){
			heap.pop();
		}
		currentnode=heap.top().second;
		currentdistance=heap.top().first;
		dist[currentnode]=currentdistance;
		visited[currentnode]=true;
		heap.pop();
		unvisited--;
		for(it=graph[currentnode].begin();it!=graph[currentnode].end();++it){
			currentpair=*it;
			if(dist[currentpair.first]==INF)
				heap.push(make_pair(currentdistance-(currentpair.second),currentpair.first));
		}
	}
	for(i=2;i<=vertices;++i){
		out<<-1*dist[i]<<" "; // le afisam cu minus pentru ca le-am bagat cu minus
	}
}

int main(){
	read();
	Dijkstra();
	return 0;
}