#include <fstream>
#include <list>
#define nmax 50005

using namespace std;

int N, M;
list<int> Neig[nmax], Cost[nmax];

void read()
{
	int x, y, c;
	ifstream fin("dijkstra.in");

	fin >> N >> M;
	
	while (M--)
	{
		fin >> x >> y >> c;
		Neig[x].push_back(y);
		Cost[x].push_back(c);
	}

	fin.close();
}

void push(int k, int Heap[], int Dist[], int Wher[])
{
	int i;

	Heap[++Heap[0]] = k;

	for (i = Heap[0]; i > 1 && Dist[Heap[i >> 1]] > Dist[k]; i >>= 1)
	{
		Wher[Heap[i] = Heap[i >> 1]] = i;
	}

	Wher[Heap[i] = k] = i;
}

bool empty(int Heap[])
{
	return Heap[0] == 0;
}

int pop(int Heap[], int Dist[], int Wher[])
{
	int k = Heap[1], i = 1, j, m, p;

	Wher[k] = 0;
	j = Heap[1] = Heap[Heap[0]--];

	while (true)
	{
		m = Dist[j];
		p = i;

		if (Heap[0] >= (i << 1) && Dist[Heap[i << 1]] < m)
		{
			m = Dist[Heap[i << 1]];
			p = i << 1;
		}

		if (Heap[0] >= (i << 1 | 1) && Dist[Heap[i << 1 | 1]] < m)
		{
			m = Dist[Heap[i << 1 | 1]];
			p = i << 1 | 1;
		}

		if (p != i)
		{
			Wher[Heap[i] = Heap[p]] = i;
			i = p;
		}
		else
		{
			if (!empty(Heap))
			{
				Wher[Heap[i] = j] = i;
			}
			
			break;
		}
	}

	return k;
}

void update(int k, int Heap[], int Dist[], int Wher[])
{
	int i;

	for (i = Wher[k]; i > 1 && Dist[Heap[i >> 1]] > Dist[k]; i >>= 1)
	{
		Wher[Heap[i] = Heap[i >> 1]] = i;
	}

	Wher[Heap[i] = k] = i;
}

void solve(int Dist[])
{
	int i, u, d; 	
	int f = numeric_limits<int>::max();
	int Heap[nmax], Wher[nmax];
	bool Visi[nmax];

	for (i = 2, Heap[1] = Wher[1] = 1, Dist[1] = Visi[1] = 0, Heap[0] = N; i <= N; ++i)
	{
		Dist[i] = f;
		Heap[i] = Wher[i] = i;
		Visi[i] = 0;
	}

	while (!empty(Heap))
	{
		u = pop(Heap, Dist, Wher);
		Visi[u] = 1;

		if (Dist[u] == f)
		{
			break;
		}

		for (list<int>::iterator i = Neig[u].begin(), j = Cost[u].begin(); i != Neig[u].end();)
		{
			if (!Visi[*i])
			{
				if ((d = Dist[u] + *j) < Dist[*i])
				{
					Dist[*i] = d;
					update(*i, Heap, Dist, Wher);
				}

				++i;
				++j;
			}
			else
			{
				i = Neig[u].erase(i);
				j = Cost[u].erase(j);
			}
		}
	}

	for (i = 2; i <= N; ++i)
	{
		if (Dist[i] == f)
		{
			Dist[i] = 0;
		}
	}
}

void write(int Dist[])
{
	int i;
	ofstream fout("dijkstra.out");

	for (i = 2; i <= N; ++i)
	{
		fout << Dist[i] << ' ';
	}

	fout << '\n';
	fout.close();
}

int main()
{
	int Dist[nmax];

	read();
	solve(Dist);
	write(Dist);
	return 0;
}