/// Craciun Catalin
///  Ubuntzei
///   OJI 2011
#include <iostream>
#include <fstream>
#include <vector>

const int NMax = 2005;
const int inf = 1<<30;

struct graf {
	
	int nod;
	int cost;
	graf *next;
};

using namespace std;

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

int n,m,k;
graf *a[NMax];
vector<int> toVisit;
int d[NMax], visited[NMax];

void add(int where, int what, int cost) {

	graf *q = new graf;
	q->nod = what;
	q->cost = cost;
	q->next = a[where];
	a[where] = q;
}

void read() {
	
	f>>n>>m;
	/*f>>k;
	for (int i=1;i<=k;i++) {
		int x; f>>x;
		toVisit.push_back(x);
	}
	*/
	
	for (int i=1;i<=m;i++) {
		int x,y,z;
		f>>x>>y>>z;
		add(x,y,z);
	}
	
	f.close();
}

void dijkstra(int startNode) {
	
	for (int i=1;i<=n;i++) {
		if (i!=startNode)
			d[i] = inf;
	}
	
	int min;
	int pmin = 0;
	for (int i=1;i<=n;i++) {
		min = inf;
		for (int j=1;j<=n;j++) {
			if (!visited[j] && min > d[j]) {
				min = d[j];
				pmin = j;
			}
		}
		
		visited[pmin] = 1;
		graf *q = a[pmin];
		
		while (q) {
			if (d[q->nod] > d[pmin] + q->cost)
				d[q->nod] = d[pmin] + q->cost;
			q=q->next;
		}
	}
	
	for (int i=2;i<n;i++) {
		if (d[i] == inf)
			g<<0<<' ';
		else
			g<<d[i]<<' ';
	} 
	if (d[n] == inf)
		g<<0<<' ';
	else
		g<<d[n]<<' ';
}

int main() {

	read();
	dijkstra(1);

	return 0;
}