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

using namespace std;

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

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 CreateHeap()
{
	posInHeap[1] = 1;
	heap[1] = make_pair(1, 0);
	dist[1] = 0;
	for (int i = 2;i <= n;++i)
	{
		dist[i] = INF;
		posInHeap[i] = i;
		heap[i] = make_pair(i, INF);
	}
	nheap = n;
}

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;
		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;
	}
}
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 Update(int node, int cost) 
{
	heap[posInHeap[node]].second = cost;
	UpHeap(posInHeap[node]);
}

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 Dijkstra()
{
	pair <int, int> x;
	while (nheap > 0)
	{
		x = heap[1];
		DeleteFromHeap(heap[1].first);
		for (auto i : graph[x.first])
		{
			if (x.second + i.second < dist[i.first])
			{
				dist[i.first] = x.second + i.second;
				Update(i.first, x.second + i.second);
			}
		}
	}
}

int main()
{
	ifstream fin("dijsktra.in");
	ofstream fout("dijsktra.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));
	}
	CreateHeap();
	Dijkstra();
	for (int i = 2;i <= n;++i)
		dist[i] == INF ? fout << 0 << " " : fout << dist[i] << " ";
	fin.close();
	fout.close();
	return 0;
}