#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

#define N 50005
#define inf (1 << 30)
#define y first
#define c second

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

typedef pair <int, int> nod;
int n, m;
vector <nod> a[N];
vector <int> d(N, inf);
priority_queue <nod, vector<nod>, greater<nod> > h;


int main()
{
	fin>>n>>m;
	while(m--)
	{
		int x, y, c;
		fin>>x>>y>>c;
		a[x].push_back(nod(y, c));
	}
	
	h.push(nod(1, 0));
	while(!h.empty())
	{
		nod x = h.top();
		h.pop();
		if (d[x.y] != inf) continue;
		d[x.y] = x.c;
		
		for(unsigned i=0; i<a[x.y].size(); i++)
			if(d[a[x.y][i].y] == inf)
				h.push(nod(a[x.y][i].y, x.c + a[x.y][i].c)); 
	}
	
	for(int i=2; i<=n; i++)
		if(d[i] != inf) fout<<d[i]<<' ';
		else fout<<"0 "; 
	return 0;
}