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

#define inf 32000
#define nmax 50002


long n,m;
long d[nmax],viz[nmax],pred[nmax];


typedef struct nod
{
	long vec,cost;
	nod *urm;
} *pNod;
pNod v[50002];

void add(pNod &dest, int b,int c)
{
	pNod p;
	p = new nod;
	p -> vec = b;
	p -> cost = c;
	p -> urm = dest;
	dest = p;
}


void citire()
{
	long i,j,x,y,c;
	ifstream in("dijkstra.in");
	in>>n;
	
	in>>m;
	for(i=1;i<=m;i++)
	{
		in>>x>>y>>c;
		add(v[x],y,c);
	}
		
}

void dj(int prim)
{
	long i,j,dmin,nod_crt;
	for(i=1;i<=n;i++)
		d[i] = inf;
	d[prim]=inf; viz[prim]=1; pred[prim]=0;
	pNod p = v[1];
	while(p)
	{
		d[p->vec]=p->cost;
		p=p->urm;
	}

	for(i=1;i<=n;i++)
	{
		dmin = inf; nod_crt;
		for(j=1;j<=n;j++)
			if(d[j]<dmin && !viz[j])
			{
				dmin=d[j];
				nod_crt=j;
			}
		viz[nod_crt]=1;


		for(j=1;j<=n;j++)
		{
			p=v[nod_crt];
			while(p && p->vec!=j)
				p=p->urm;
			
			if(p && !viz[j] && d[j]>dmin+p->cost)
			{
				d[j]=dmin+p->cost;
				pred[j]=nod_crt;
			}
		}

	}


}


ofstream out("dijkstra.out");
void afisare()
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		j=i;
		if(d[j]<inf)
			out<<d[j]<<" ";
		else
			out<<"0 ";
		/*
		out<<j<<" ";
		while(pred[j])
		{
			out<<pred[j]<<" ";
			j=pred[j];
		}
		out<<endl;
		*/
	}
}

int main()
{
	citire();
	dj(1);
	afisare();
}