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

using namespace std;

int N, M;
vector<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;
	int Heap[nmax], Wher[nmax];
	
	for (i = 2, Heap[0] = Dist[1] = 0; i <= N; ++i)
	{
		Dist[i] = numeric_limits<int>::max();
		push(i, Heap, Dist, Wher);
	}

	push(1, Heap, Dist, Wher);

	while (!empty(Heap))
	{
		u = pop(Heap, Dist, Wher);

		if (Dist[u] == numeric_limits<int>::max())
		{
			break;
		}

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

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

	for (i = 2; i <= N; ++i)
	{
		Dist[i] = (Dist[i] == numeric_limits<int>::max()? 0: Dist[i]);
		fout << Dist[i] << ' ';
	}

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

int main()
{
	int Dist[nmax];

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