#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

#define MAXNODES 5000

const long long inf=5e9;

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

struct edge{
	int destination;
	int length;
};

struct node{
	int index;
	long long distance;
};


struct comparator{
	bool operator()(const node&a,const node&b){
		return a.distance>b.distance;

	}
};


int num_nodes,num_edges;
long long dist[MAXNODES];
vector<edge> graph[MAXNODES];
priority_queue<node,vector<node>,comparator> que;



void read(){
	in>>num_nodes>>num_edges;
	int origin,destination,cost;
	for(int i=0;i<num_edges;i++){
		in>>origin>>destination>>cost;
		graph[origin-1].push_back({destination-1,cost});
	}

	for(int i=0;i<num_nodes;i++){
		dist[i]=inf;
	}
}


void dijkstra(){
	que.push({0,0});
	while(!que.empty()){
		node top=que.top();	
		que.pop();
		if(top.distance>=dist[top.index])
			continue;
		
		dist[top.index]=top.distance;

		for(const edge&eg:graph[top.index]){
			if(top.distance+eg.length<dist[eg.destination]){
				que.push({eg.destination,top.distance+eg.length});
			}
		}
	}

	for(int i=1;i<num_nodes;i++)
		if(dist[i]==inf)
			out<<0<<" ";
		else
			out<<dist[i]<<" ";

}


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