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

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

# define nmax 50001
# define inf 5000000

typedef struct structura{int v,d;};

vector <structura> nod[nmax];
int n,m,st[nmax],l,km[nmax];
structura aux;bool viz[nmax];

void citire()
{
	f>>n>>m; int i,j,dist;
	for(i=1;i<=m;i++)
	{
		f>>i>>j>>dist;
		aux.v=j;aux.d=dist;
		nod[i].push_back(aux);
	}
}

int main()
{
	citire();
	st[1]=viz[1]=1;
	int pi=1,pj=1,i,j,vec;
	memset(km,inf,sizeof(km));
	
	while(pi<=pj)
	{
		i=st[pi];km[1]=0;
		l=nod[i].size();
		for(j=1;j<=l;j++)
		{
			vec=nod[i][j].v;
			
			if(!viz[vec]&&km[vec]>km[i]+nod[i][j].d)
			{
				km[vec]=km[i]+nod[i][j].d;
				pj++;st[pj]=vec;
			}
		}viz[i]=1;
		pi++;
	}
	for(i=2;i<=n;i++)
		g<<km[i]<<" ";
}