#include<fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct NodGR
{
	int inf,pd;
	struct NodGR* next;
};

typedef NodGR* NGR;

NGR a[50001];
int viz[50001],C[500001],N,M,i;

void read();
void solve();
void adaug(int x,int y,int p);
void DJK(int x);

int main()
{
	freopen ("dijkstra.in","r",stdin);
	freopen ("dijkstra.out","w",stdout);
	read();
	for (i=1;i<=N;viz[i++]=50000001);
	DJK(1);
	for (i=2;i<=N;++i)
	{
		if (viz[i]==50000001) viz[i]=0;
		g<<viz[i]<<' ';
	}
	f.close();
	g.close();
	return 0;
}

void adaug(int x,int y,int p)
{
	NGR q=new NodGR;
	q->inf=y;
	q->pd=p;
	q->next=a[x];
	a[x]=q;
}

void read()
{
	int x,y,p;
	f>>N>>M;
	for (i=1;i<=M;++i)
	{
		f>>x>>y>>p;
		adaug(x,y,p);
	}
}

void DJK(int x)
{
	NGR i;
	int p,u,z;
	p=u=1;
	C[p]=x;
	viz[x]=0;
	while (p<=u)
	{
		z=C[p++];
		for (i=a[z];i;i=i->next)
			if (viz[i->inf]>viz[z]+i->pd)
			{
				C[++u]=i->inf;
				viz[i->inf]=viz[z]+i->pd;
			}
	}
}