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

using namespace std;

int N, M;
vector< pair<int, int> > Neig[nmax];

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

	fin >> N >> M;
	
	while (M--)
	{
		fin >> x >> y >> c;
		Neig[x].push_back(pair<int, int>(y, 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 = Heap[1] = Heap[Heap[0]--], p = i << 1;

	while (Heap[0] >= p)
	{
		p = i << 1;

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

		if (Dist[Heap[p]] < Dist[j])
		{
			Wher[Heap[i] = Heap[p]] = i;
			i = p;
			p = i << 1;
		}
		else
		{
			break;
		}
	}

	Wher[Heap[i] = j] = i;
	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 f)
{
	int i, u, d; 	
	int Heap[nmax], Wher[nmax];
	bool Visi[nmax];

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

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

		for (vector< pair<int, int> >::iterator i = Neig[u].begin(); i != Neig[u].end(); ++i)
		{
			if (!Visi[i->first] && (d = Dist[u] + i->second) < Dist[i->first])
			{
				Dist[i->first] = d;
				update(i->first, Heap, Dist, Wher);
			}
		}
	}
}

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

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

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

int main()
{
	int Dist[nmax], f = numeric_limits<int>::max();

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