#include<bits/stdc++.h>
using namespace std;

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

int num_nodes,num_edges;
const int inf=1e9;

struct edge{
	int destination,cost;
};

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

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

vector<edge> graph[50000];
int min_cost[50000];


void read(){
	in>>num_nodes>>num_edges;
	int a,b,c;
	for(int i=0;i<num_edges;i++){
		in>>a>>b>>c;
		graph[a-1].push_back({b-1,c});
	}
	for(int i=0;i<num_nodes;i++)
		min_cost[i]=inf;
}


void dijkstra(){
	priority_queue<node,vector<node>,comparator> que;
	min_cost[0]=0;
	que.push({0,0});
	while(que.size()){
		node here=que.top();
		que.pop();
		if(min_cost[here.index]<here.cost)
			continue;


		for(int i=0;i<graph[here.index].size();i++){
			int there=graph[here.index][i].destination;
			int cost=graph[here.index][i].cost;
				
			if(here.cost+cost<min_cost[there]){
				min_cost[there]=here.cost+cost;
				que.push({there,min_cost[there]});
			}
		}

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


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