#include <fstream>
#include <iostream>
#include <string>

#include <vector>

using namespace std;


const string file = "dijkstra";

const string infile = file + ".in";
const string outfile = file + ".out";

int N;
int M;

#define NMAX 50002
#define INF 1<<30

int drum[NMAX];
bool viz[NMAX];
vector< pair < int, int> > G[NMAX];


void citire()
{
	
	fstream fin(infile.c_str(), ios::in);

	fin >> N >> M;

	int x;
	int y;
	int c;

	
	for(int i = 0; i < M; i++)
	{
		fin >> x >> y >> c;
		G[x - 1].push_back(make_pair(y - 1 , c));

	}

	fin.close();

	for(int i = 1; i < N; i++)
	{
		drum[i] = INF;
	}

}


int heap[NMAX];
int heapPoz[NMAX];
int heapSize;
inline int parrent(int l)
{
	return l >> 1;
}


inline int lSon(int l)
{
	return (l << 1);
}

inline int rSon(int l)
{
	return (l << 1) + 1;
}




void swapHeap(int a, int b)
{
	int aux = heap[a];
	heap[a] = heap[b];
	heap[b] = aux;

	heapPoz[heap[a]] = a;
	heapPoz[heap[b]] = b;

}

void pushHeap(int l)
{
	if(l == 1)
		return;

	int p = parrent(l);

	if(drum[heap[p]] > drum[heap[l]])
	{
		swapHeap(l, p);
		pushHeap(p);
	}
}


void downHeap(int l)
{
	int leftS = lSon(l);
	int rightS = rSon(l);
	int minim = l;
	
	if(leftS <= heapSize && drum[heap[leftS]] < drum[heap[minim]])
	{
		minim = leftS;
	}
	if(rightS <= heapSize && drum[heap[rightS]] < drum[heap[minim]])
	{
		minim = rightS;
	}
	
	if(minim != l)
	{
		swapHeap(l, minim);
		downHeap(minim);
	}

	
}


void insertHeap(int value)
{
	heapSize++;
	heap[heapSize] = value;
	heapPoz[value] = heapSize;

	pushHeap(heapSize);
}

int popHeap()
{
	if(heapSize == 0) 
		return -1;

	int result = heap[1];

	swapHeap(1, heapSize);
	heapSize--;
	downHeap(1);

	return result;
}



void solve()
{
	insertHeap(0);
	int current;

	while(heapSize != 0)
	{

		current = popHeap();
		viz[current] = true;


		for(vector<pair<int, int> >::iterator itr = G[current].begin();
			itr != G[current].end();
			itr++)
		{

			if(viz[itr->first])
				continue;


			if(drum[itr->first] > drum[current] + itr->second)
			{
				drum[itr->first] = drum[current] + itr->second;

				if(heapPoz[itr->first] == 0)
				{
					
					insertHeap(itr->first);
				}
				else
				{
					pushHeap(heapPoz[itr->first]);
				}

			}
		}

	}


}


void afisare()
{

	fstream fout(outfile.c_str(), ios::out);

	for(int i = 1; i < N; i++)
	{
		fout << ((drum[i] == INF) ? 0 : drum[i] ) << " ";
	}

	fout.close();
}

int main()
{
	citire();
	solve();
	afisare();

}