#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;

class heapp
{	int h[50001];
	int dim;
	public:
		heapp() { dim = 0; h[0] = INF; }
		
		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];
		}
}heap;

void dijkstra()
{	int x;
	for(int i = 2; i <= N; i++)
		d[i] = INF;
	d[1] = 0; in[1] = 1; heap.push(1);
	while(!heap.empty())
	{	x = heap.min(); heap.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 , heap.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;
}