#include <bitset>
#include <fstream>
#include <vector>
#include <queue>
#define push(X,D) 		\
{						\
	d[X]=D;				\
	if(!inCoada[X])		\
		coada.push(X),	\
		inCoada[X]=true;\
}

using namespace std;
const unsigned int NMAX=50001,DMAX=250000000;
typedef pair<unsigned int,unsigned int> pereche;

unsigned int N,M;
vector<pereche> G[NMAX];
vector<unsigned int> d(NMAX,DMAX);

void citire()
{
	unsigned int s,d,c;
	ifstream fin("dijkstra.in");
	fin>>N>>M;
	for(unsigned int i=0;i<M;i++)
	{
		fin>>s>>d>>c;
		G[s].push_back(pereche(d,c));
	}
	fin.close();
}

void rezolvare()
{
	queue<int> coada;
	bitset<NMAX> inCoada(false);
	push(1,0);
	while(!coada.empty())
	{
		int tata=coada.front();
		coada.pop();
		for(vector<pereche>::iterator i=G[tata].begin();i!=G[tata].end();i++)
			if(d[i->first]>d[tata]+i->second)
				push(i->first,d[tata]+i->second);
		inCoada[tata]=false;
	}
}

void afisare()
{
	ofstream fout("dijkstra.out");
	for(unsigned int i=2;i<=N;i++)
		fout<<(d[i]!=DMAX?d[i]:0)<<" ";
	fout<<endl;
}

int main()
{
	citire();
	rezolvare();
	afisare();
	return 0;
}