#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct Pair {
	int x, dist;
	
	friend bool operator < (const Pair& a, const Pair& b)
	{
		return a.dist > b.dist;
	}
};

template<class T>
class Priority_queue {
public:
	Priority_queue() : n {0}, heap {vector<T>(1)}
	{}
	
	void push(const T& val)
	{
		n++;
		heap.emplace_back(val);
		percolate(n);
	}
	
	T pop()
	{
		T val = heap[1];
		swap<T>(heap[1], heap[n]);
		n--;
		heap.pop_back();
		sift(1);
		return val;
	}
	
	T top() const
	{
		return heap[1];
	}
	
	bool empty() const
	{
		return n == 0;
	}
	
private:
	void percolate(int pos)
	{
		while (pos > 1 && heap[pos / 2] < heap[pos])
		{
			swap<T>(heap[pos], heap[pos / 2]);
			pos /= 2;
		}
	}

	void sift(int pos)
	{
		if (pos > n || pos < 1)
			return;
		
		int son;
		do
		{
			son = 0;
			if (2 * pos <= n)
			{
				son = 2 * pos;
				if (2 * pos + 1 <= n && heap[2 * pos] < heap[2 * pos + 1])
					son = 2 * pos + 1;
				if ( !(heap[pos] < heap[son]) )
					son = 0;
			}
			if (son)
			{
				swap<T>(heap[pos], heap[son]);
				pos = son;
			}
		} while (son);
	}

	int n;
	vector<T> heap;
};

using PI = pair<int, int>;
using VP = vector<PI>;
using VVP = vector<VP>;
using VI = vector<int>;

const int Inf = 0x3f3f3f3f;
int n, m;
VVP G;
VI d;

void Read();
void Dijkstra(int x, VI& d);
void Write();

int main()
{
	Read();
	Dijkstra(1, d);
	Write();
}

void Dijkstra(int x, VI& d)
{
	d = VI(n + 1, Inf);
	Priority_queue<Pair> Q;
	d[x] = 0;
	Q.push({x, 0});
	
	int y, dx, w;
	while (!Q.empty())
	{
		x = Q.top().x;
		dx = Q.top().dist;
		Q.pop();
		if (dx > d[x])
			continue;
		for (const PI& p : G[x])
		{
			y = p.first;
			w = p.second;
			if (d[y] > d[x] + w)
			{
				d[y] = d[x] + w;
				Q.push({y, d[y]});
			}
		}
	}
}

void Write()
{
	ofstream fout("dijkstra.out");
	for (int i = 2; i <= n; i++)
		if (d[i] != Inf)
			fout << d[i] << ' ';
		else
			fout << "0 ";
}

void Read()
{
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	G = VVP(n + 1);
	
	int x, y, w;
	for (int i = 0; i < m; i++)
	{
		fin >> x >> y >> w;
		G[x].emplace_back(y, w);
	}
}