#include<fstream>
#include<vector>
#include<queue>
#include<climits>

using namespace std ;

int n;
vector< vector< pair<int,int> > > edges;
vector<int> cost;
vector<int> predecessor;
void readData(){

	int m;
	ifstream in("dijkstra.in");
	in>>n>>m;
	int node1,node2,cost;
	edges.resize(n+1);
	for(int i=0;i<m;i++){
		in>>node1>>node2>>cost;
		edges[node1].push_back(make_pair(node2,cost));
	}
	
	in.close();
}

void dijkstra(int start,int dest){
	vector<bool> viz(n+1);
	cost.resize(n+1);
	predecessor.resize(n+1);
	for(int i=0;i<cost.size();i++){
		viz[i] = 0;
		cost[i] = INT_MAX;
	}
	
	priority_queue< pair<int,int> , vector< pair<int,int> >, greater<pair<int,int> > > Q;

	cost[start] = 0;
	Q.push(make_pair(cost[start],start));
	
	predecessor[start] = -1;
	while(!Q.empty()){
		int current = Q.top().second;
		//if(current == dest) return;
		Q.pop();

		if(! viz[current]){

			for(vector<pair<int,int> >::iterator it = edges[current].begin();it!=edges[current].end();it++){				
				if(cost[it->first] > cost[current] + it->second){
					cost[it->first] = cost[current] + it->second;
					//predecessor[it->first] = current ;
					Q.push(make_pair(cost[it->first],it->first));					
				}

			}		
			viz[current] = true;
		}		
	}
}

void paths(int dest,vector<int> &path){
	if(predecessor[dest]!= -1){
		path.push_back(predecessor[dest]);
		paths(predecessor[dest],path);
	}
}

int main(){
	
	ofstream out("dijkstra.out");	
	
	readData();
	dijkstra(1,-1);
	for(int i=2;i<cost.size();i++){
		if(cost[i]==INT_MAX) 
			cost[i] = 0; 
		out<<cost[i]<<" ";
	}
	//vector<int> path;

	//paths(3,path);
	//for(int i=path.size()-1;i>=0;i--)
		//out<<path[i]<<" ";
	out.close();
	return 0 ;
}