#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(! viz[current]){
			
			for(int i=0;i<edges[current].size();i++){				
				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(make_pair(cost[edges[current][i].first],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,-1);
	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 ;
}