#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>
#include <cstdio>
#define inf (1<<30)-1
using namespace std;


struct node{
	int nextNode;
	int cost;
	node(int aNode,int aCost){
		nextNode = aNode;
		cost = aCost;
	}	
};

int n,m;
vector<node>G[50005];
int dist[50005];

class CMP{
public:
	bool operator()(int a,int b){
		return dist[a] > dist[b];
	}

};

priority_queue<int, vector<int>, CMP> pq;
bool mark[50005];
void dijkstra(int start){
	for(int i = 0 ; i <= n ;i ++)
		dist[i] = inf;
	
	dist[start] = 0;
	for(int i = 0 ; i < G[start].size(); i++){
		dist[G[start][i].nextNode] = G[start][i].cost;
	}
	for(int i =2 ; i <= n ; i++){
		if(!(dist[i] == inf))
		pq.push(i);
	}
	mark[start] = true;
	while(!pq.empty()){
		int top = pq.top();
		pq.pop();
		for(int i = 0 ;i < G[top].size(); i++){
			int nextNode = G[top][i].nextNode;
			if(!mark[nextNode]){
				if(dist[nextNode] > dist[top] + G[top][i].cost){
					dist[nextNode] = dist[top] + G[top][i].cost;
					pq.push(nextNode);
				}
			}
		}
		mark[top] = true;
	}

	for(int i = 2; i <= n; i++){
		if(dist[i] == inf)
			cout << 0 << " ";
		else
		cout << dist[i] << " ";
	}
	cout << endl;
}

void read(){

	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int x,y,c;
		cin >> x >> y >> c;
		G[x].push_back(node(y,c));
	}	
}

int main(){

	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	dijkstra(1);
	return 0;
}