#include <stdio.h>
#include <queue>
#include <vector>
#define MAX 50005
#define INF 10000007
using namespace std;

typedef struct{
	int node, cost;
} TNod;

struct compar{
	bool operator() (TNod a, TNod b) { return a.cost > b.cost;}
};

priority_queue<TNod, vector<TNod>, compar> q;
vector<TNod> v[MAX];
bool viz[MAX];
int d[MAX], i, n, m, x, y, z;

void dijkstra(int s){
	for(i = 1; i <= n; i++)
		d[i] = INF;
	d[s] = 0;
	TNod aux;
	aux.node = s;
	aux.cost = d[s];
	q.push(aux);

	while(!q.empty()){
		int x = q.top().node;
		q.pop();

		if(viz[x]) continue;
		viz[x] = 1;

		while(!v[x].empty()){
			aux = v[x].back();
			v[x].pop_back();
			if(d[x] + aux.cost < d[aux.node]){
				d[aux.node] = d[x] + aux.cost;
				aux.cost = d[aux.node];
				q.push(aux);
			}
		}
	}
}

int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	TNod aux;
	scanf("%d%d", &n, &m);
	for(i = 0; i < m; i++){
		scanf("%d%d%d", &x, &y, &z);
		aux.node = y;
		aux.cost = z;
		v[x].push_back(aux);
	}

	dijkstra(1);

	for(i = 2; i <= n; i++)
		printf("%d ", d[i] == INF ? 0 : d[i]);
	printf("\n");
	return 0;
}