#include<fstream>
#include<vector>
#include<bitset>
using namespace std;

#define INF 2147483647

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

struct nod
{	int to,cost;
	nod(int y,int c)
	{	to = y , cost = c; }
};
typedef vector<nod>::iterator it;
vector<nod>a[50001];
bitset<50001>in;
int d[50001];
int N,M;

int h[50001];
int dim;

void up_heap(int),down_heap(int);

void push(int x)
{	h[++dim] = x;
	up_heap(dim);
}
	
void pop()
{	swap(h[1],h[dim]);
	dim--; if(dim == 0) return;
	down_heap(1);
}
		
void up_heap(int poz)
{	int key = d[h[poz]];
	while(key <= d[h[poz / 2]] && poz != 1)
		swap(h[poz],h[poz / 2]) , poz /= 2;
}
		
void down_heap(int poz)
{	int key = d[h[poz]],p1;
	while(((2 * poz <= dim && key >= d[h[2 * poz]]) || (2 * poz + 1 <= dim && key >= d[h[2 * poz + 1]])) && poz != dim)
	{	if(2 * poz <= dim) p1 = 2 * poz;
		if(2 * poz + 1 <= dim)
			if(d[h[p1]] > d[h[2 * poz + 1]])
				p1 = 2 * poz + 1;
		swap(h[poz],h[p1]); poz = p1;
	}
}
		
bool empty()
{	return dim == 0;
}
		
int min()
{	return h[1];
}

void dijkstra()
{	int x;
	for(int i = 2; i <= N; i++)
		d[i] = INF;
	d[1] = 0; in[1] = 1; push(1);
	while(!empty())
	{	x = min(); pop(); in[x] = 0;
		for(it i = a[x].begin(); i != a[x].end(); i++)
			if(d[i->to] > d[x] + i->cost)
			{	d[i->to] = d[x] + i->cost;
				if(!in[i->to])
					in[i->to] = 1 , push(i->to);
			}
	}
	for(int i = 2; i <= N; i++)
		g<<(d[i] == INF?0:d[i])<<" ";
}

int main()
{	int i,x,y,c;
	f>>N>>M;
	for(i = 1; i <= M; i++)
	{	f>>x>>y>>c;
		a[x].push_back(nod(y,c));
	}
	dijkstra();
	f.close();
	g.close();
	return 0;
}