#include <fstream>

/////////////////////
#include <vector>
////////////////////

#define NMAX 50001
#define INF 2000000000
#define InFile "graf.in"
#define OutFile "graf.out"

using namespace std;

struct Arc {short int vf; int c;};

///////////////////////
vector <Arc> G[NMAX];
//////////////////////

int n, x0, lgh;
int dmin[NMAX];
int poz[NMAX];
int h[NMAX];

void Citire();
void InitHeap();
void Dijkstra();
void Afisare();

int main()
{
Citire();
InitHeap();
Dijkstra();
Afisare();
return 0;
}


void Citire()
{int m, i, x;
Arc crt;
ifstream fin(InFile);
fin>>n>>m;
x0=1;
for (i=0; i<m; i++)
	{fin>>x>>crt.vf>>crt.c;
	 G[x].push_back(crt);
	}
}

void CombHeap(int i)
//combin heapul cu radacina 2i cu cel cu radacina 2i+1 si cu vf i
{
int tata=i, aux;
int fiu=2*tata;
while (fiu<=lgh)
	{
	if (fiu<lgh && dmin[h[fiu+1]]<dmin[h[fiu]]) fiu++;
	if (dmin[h[tata]]>dmin[h[fiu]])
		{poz[h[tata]]=fiu; poz[h[fiu]]=tata;
		aux=h[tata]; h[tata]=h[fiu]; h[fiu]=aux;
		tata=fiu;
		fiu=2*tata;
		}
		else break;
	}
}

void InitHeap()
{int i, j;
for (i=1; i<=n; i++) {dmin[i]=INF; h[i]=i; poz[i]=i;}
lgh=n;
for (j=0; j<G[x0].size(); j++)
	dmin[G[x0][j].vf]=G[x0][j].c;
dmin[x0]=0;
for (i=n/2; i>=1; i--) CombHeap(i);
}

int ExtrageMin()
{int minim=h[1];
 h[1]=h[lgh]; lgh--; poz[h[1]]=1; poz[minim]=-1;
 CombHeap(1);
 return minim;
}

void Upgrade(int fiu)
{
int tata=fiu/2, aux;
while (tata > 0 && dmin[h[tata]] > dmin[h[fiu]])
	{
	poz[h[tata]]=fiu; poz[h[fiu]]=tata;	
    aux=h[tata]; h[tata]=h[fiu]; h[fiu]=aux; 
	fiu=tata;
	tata=fiu/2;
	}	
}

void Dijkstra()
{int i, j, vfmin;
for (i=0; i<n; i++)
	{vfmin=ExtrageMin();
     for (j=0; j<G[vfmin].size(); j++)
		 if (poz[G[vfmin][j].vf]!=-1) //il mai am in heap
			 if (dmin[G[vfmin][j].vf]>dmin[vfmin]+G[vfmin][j].c)
				 {dmin[G[vfmin][j].vf]=dmin[vfmin]+G[vfmin][j].c;
			     Upgrade(poz[G[vfmin][j].vf]);
				 }
	}

}	
	
void Afisare()
{
int i;
ofstream fout(OutFile);
for (i=2; i<=n; i++)
     fout<<dmin[i]<<' ';
fout<<'\n';
fout.close();
}