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

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int Inf = 0x3f3f3f3f;
vector<int> D;
vector<vector<pair<int, int> > > G; 
int n, m;
bool inHeap;


struct Heap {
	Heap(int n = 0) : nH(0), H(vector<int>(n + 1)) , P(vector<int>(n + 1))
	{}
	void pop()
	{
		H[1] = H[nH--]; P[H[1]] = 1;//
		
		int p = 1, s = 2;
		while ( s <= nH )
		{
			if ( s + 1 <= nH && D[H[s + 1]] < D[H[s]] )
				s++;
			if ( D[H[s]] < D[H[p]] )
			{
				Swap(s, p);
				p = s;
				s = 2 * p;
			}
			else break;
		}
	}
	
	void push(int node)
	{
		H[++nH] = node;	P[node] = nH;
		up(nH);
	}
//	void up(int node)
	void up(int poz)
	{
		int s = poz, p = s / 2;
		while ( p != 0 && D[H[s]] < D[H[p]])
		{
			Swap(p, s);
			s = p; p = s / 2;
		}
	}
	
	void Swap(int s, int p)
	{
		swap(H[p], H[p]);
		P[H[p]] = p;
		P[H[s]] = s;
	}
	
	bool empty() const
	{
		return nH <= 0;
	}
	int top() const
	{
		return H[1];
	}
	int nH;
	vector<int> H, P;
};


void Dijkstra(int k, vector<int>& D);
void Read();
void Write();

int main()
{
	Read();
	Dijkstra(1, D);
	Write();
	fout.close();
	return 0;
}

void Dijkstra(int k, vector<int>& D)
{
	Heap heap(n);
	int x, w;
	D = vector<int>(n + 1, Inf);
	D[k] = 0; 
	heap.push(k);
	while ( !heap.empty() )
	{
		k = heap.top();
		heap.pop();
		
		for (const auto& p : G[k]) 
		{
			x = p.first, w = p.second;
			if (D[x] > D[k] + w)
			{
				inHeap = (D[x] != Inf); 
				D[x] = D[k] + w;
				if (inHeap) // x e in heap
					heap.up(heap.P[x]);
				else
					heap.push(x);
			}
		}
	}
}

void Read()
{
	fin >> n >> m;
	G.resize(n + 1);
	int a, b, cost;
	for (int i = 0; i < m; ++i)
	{
		fin >> a >> b >> cost;
		G[a].push_back({b, cost});
	}
	fin.close();
}

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