#include<fstream>
#include<algorithm>
#include<iterator>
using namespace std;

const int INF = 1000000000;

struct nod
{
	pair<int, int> next[50001];
	int many;
	nod()
	{
		many = 0;
	}
};
nod* a;
int n, m, poz[50001], d[50001];
bool s[50001];
int* h, sz;

void read();
void write();
void dijkstra();
void push(int x);
void moveup(int x);
void extract();

int main()
{
	read();
	dijkstra();
	write();
	return 0;
}

void read()
{
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	a = new nod [n + 1], h = new int [n + 1];

	int p1, p2, cost;
	
	d[1] = 0;
	for (int i = 2; i <= n; ++i)
	{
		d[i] = INF;
	}
	for (int i = 1; i <= m; ++i)
	{
		fin >> p1 >> p2 >> cost;
		a[p1].next[++a[p1].many] = make_pair(p2, cost);
		if (p1 == 1)
		{
			d[p2] = cost;
		}
	}
	for (int i = 2; i <= n; ++i)
		push(i);
}

void dijkstra()
{
	s[1] = true;
	
	int now, k;
	for (now = 2; now <= n; ++now)
	{
		k = h[1];
		s[k] = true;
		extract();
		
		for (int i = 1; i <= a[k].many; ++i)
			if (s[a[k].next[i].first] == false && d[a[k].next[i].first] > d[k] + a[k].next[i].second)
			{
				d[a[k].next[i].first] = d[k] + a[k].next[i].second;
				moveup(a[k].next[i].first);
			}
	}
}

void write()
{
	ofstream fout("dijkstra.out");
	copy(d + 2, d + n + 1, ostream_iterator<int>(fout, " "));
}

void push(int x)
{
	h[++sz] = x;
	int f = sz, t = f >> 1;
	while (t > 0)
		if (d[h[f]] < d[h[t]])
		{
			swap(h[f], h[t]);
			poz[h[t]] = t;
			poz[h[f]] = f;
			
			t >>= 1, f >>= 1;
		}
		else
			break;
}

void moveup(int x)
{
	int f = poz[x], t = poz[x] << 1;
	while (t > 0)
		if (d[h[f]] < d[h[t]])
		{
			swap(h[f], h[t]);
			poz[h[t]] = t;
			poz[h[f]] = f;
			
			t >>= 1, f >>= 1;
		}
		else
			break;
}

void extract()
{
	h[1] = h[sz--];
	int t = 1, f = 2;
	while (f <= sz)
	{
		if (f + 1 <= sz)
			f = d[h[f]] < d[h[f + 1]] ? f : f + 1;
		if (d[h[f]] < d[h[t]])
		{
			swap(h[f], h[t]);
			poz[h[f]] = f;
			poz[h[t]] = t;
			
			t <<= 1, f <<= 1;
		}
		else
			break;
	}
}