//#include <iostream>
//#include <conio.h>

#include <algorithm>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

const int DIM = 5e4 + 10;
const int INF = 2e9;
int n, m;
vector <pair <int, int> > graph[DIM];
bitset <DIM> viz;
int dist[DIM];
pair <int, int> heap[DIM];
int posInHeap[DIM];
int nheap;

inline int LeftSon(const int& x)
{
	return 2 * x;
}

inline int RightSon(const int& x)
{
	return 2 * x + 1;
}

inline int Father(const int& x)
{
	return x / 2;
}

void UpHeap(int x)
{
	while (x > 1 && heap[Father(x)].second > heap[x].second)
	{
		swap(posInHeap[heap[Father(x)].first], posInHeap[heap[x].first]);
		swap(heap[Father(x)], heap[x]);
		x = Father(x);
	}
}

void DownHeap(int x)
{
	while (true)
	{
		int sonMin = -1;
		if (LeftSon(x) <= nheap)
			sonMin = LeftSon(x);
		if (RightSon(x) <= nheap && heap[RightSon(x)].second < heap[LeftSon(x)].second)
			sonMin = RightSon(x);
		if (sonMin == -1)
			break; // inseamna ca nu mai are fii
		if (heap[sonMin].second < heap[x].second)
		{
			swap(posInHeap[heap[sonMin].first], posInHeap[heap[x].first]);
			swap(heap[sonMin], heap[x]);
			x = sonMin;
		}
		else
			break; // inseamna ca fiii lui sunt mai mici decat el
	}
}

void InsertInHeap(pair <int, int> x)
{
	heap[++nheap] = x;
	posInHeap[x.first] = nheap;
	UpHeap(posInHeap[x.first]);
}

void DeleteFromHeap(int node)
{
	int aux = posInHeap[node];
	heap[posInHeap[node]] = heap[nheap];
	posInHeap[heap[nheap].first] = posInHeap[node];
	posInHeap[node] = -1;
	--nheap;
	UpHeap(aux);
	DownHeap(aux);
}

void Dijsktra()
{
	dist[1] = 0;
	InsertInHeap(make_pair(1, 0));
	pair <int, int> x;
	while (nheap > 0)
	{
		x = heap[1];
		DeleteFromHeap(x.first);
		viz[x.first] = 1;
		for (auto i : graph[x.first])
		{
			if (viz[i.first] == 0 && x.second + i.second < dist[i.first])
			{
				if (posInHeap[i.first] != -1)
					DeleteFromHeap(i.first);
				dist[i.first] = x.second + i.second;
				InsertInHeap(make_pair(i.first, x.second + i.second));
			}
		}
	}
}

int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin >> n >> m;
	int a, b, c;
	for (int i = 1;i <= m;++i)
	{
		fin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
	}
	/*for (int i = 1;i <= n;++i, cout << "\n")
		for (int j = 0;j < graph[i].size();++j)
			cout << graph[i][j].first << "," << graph[i][j].second << " ";*/
	for (int i = 1;i <= n;++i)
	{
		dist[i] = INF;
		posInHeap[i] = -1;
	}
	Dijsktra();
	for (int i = 2;i <= n;++i)
		dist[i] == INF ? fout << 0 << " " : fout << dist[i] << " ";
	fin.close();
	fout.close();
	//_getch();
	return 0;
}