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

typedef struct{
	int to, cost;
} nod;

#define nMax 50001
#define inf 0x3f3f3f3f

vector<nod> G[nMax];
int d[nMax];
int n,m;

nod new_nod(int x, int y){
	nod rez;
	rez.to = x, rez.cost = y;
	return rez;
}

void citire(char file[]){
	ifstream fin(file);
	fin >> n >> m;
	for (int i=0;i<m;i++){
		int a, b, c;
		fin >> a >> b >> c;
		G[a-1].push_back(new_nod(b-1,c));
	}
}

void solve(int root){
	int v[nMax];
	memset(d, inf, sizeof(d));
	memset(v, false, sizeof(v));

	d[root] = 0;

	queue<int> q;
	q.push(root);
	while (!q.empty()){
		int a = q.front();
		q.pop();
		v[a] = false;
		for (vector<nod>::iterator it = G[a].begin(); it!=G[a].end(); it++){
			int b = (*it).to, c = (*it).cost;
			if (d[a] + c < d[b]){
				d[b] = d[a] + c;
				if (!v[b])
					q.push(b), v[b] = true;
			}
		}
	}
}

void scriere(char file[]){
	ofstream fout(file);
	for (int i=1;i<n;i++)
		fout << (d[i] < inf?d[i]:0) << " ";
	fout.close();
}

int main(){
	citire("dijkstra.in");
	solve(0);
	scriere("dijkstra.out");
	return 0;
}