#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define N_MAX 50002

struct nod{
	int cost, x;
	nod(int x, int cost){
		this->cost = cost;
		this->x = x;
	}
};


int n, m;
int cost[N_MAX];
vector <nod> graph[N_MAX];
bool inqueue[N_MAX];

struct cmp{
	bool operator () (const int &a, const int &b) const{
		return cost[a] > cost[b];
	}
};

priority_queue <int, vector <int>, cmp> Q;
int x, y, z;


void dijkstra(int start){
	for(int i = 1; i <= n; i ++)
		cost[i] = (1 << 30);
	cost[start] = 0;
	inqueue[start] = true;
	Q.push(start);
	
	vector <nod> :: iterator it;
	while(!Q.empty()){
		int nd = Q.top();	Q.pop();
		inqueue[nd] = false;
		for(it = graph[nd].begin(); it != graph[nd].end(); it ++){
			if(cost[it->x] <= cost[nd] + it->cost)
				continue;
			cost[it->x] = cost[nd] + it->cost;
			if(!inqueue[it->x]){
				Q.push(it->x);
				inqueue[it->x] = true;
			}
		}
	}
}

int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i ++){
		scanf("%d %d %d", &x, &y, &z);
		graph[x].push_back(nod(y, z));
	}
	
	dijkstra(1);
	
	for(int i = 2; i <= n; i ++)
		printf("%d ", cost[i] == (1 << 30) ? 0 : cost[i]);
	
	return 0;
}