#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();
}

class compare_cost{
public :
	bool operator()(int &node1,int&node2){
		return(cost[node1]>cost[node2]);
	}
};

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++)
		cost[i]=INT_MAX;
	
	priority_queue<int , vector<int>, compare_cost> Q;
	Q.push(start);
	cost[start] = 0;
	predecessor[start] = -1;
	while(!Q.empty()){
		int current = Q.top();
		
		if(! viz[current]){
			
			for(int i=0;i<edges[current].size();i++){
				if(!viz[edges[current][i].first]){
					if(cost[edges[current][i].first] > cost[current] + edges[current][i].second){
						cost[edges[current][i].first] = cost[current] + edges[current][i].second;
						//predecessor[edges[current][i].first] = current ;
						Q.push(edges[current][i].first);
					}
				}
			}
		}
		viz[current] = true;
		if(current == dest) return;
		Q.pop();
	}
}
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,3);
	for(int i=2;i<cost.size();i++)
		if(cost[i]==INT_MAX) 
			out<<"0 "; 
		else 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 ;
}