#include <fstream>
#define NMAX 1001
#define INF 10000001

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct Arc
{
    int vf, c;
} G[NMAX][NMAX];
int n, x0;
int dmin[NMAX]; //distantele minime
int prec[NMAX]; //pot reconstitui drumul
int M[NMAX];//multimea varfurilor selectate
int h[NMAX], lgh; //in h sunt vf organizate ca min-heap
int poz[NMAX];// poz[i]=-1 daca vf i nu a fost pus in heap, altfel

void citire();
void dijkstra();
int ExtractMin();
void InsertHeap(int vf);
void Upgrade(int fiu );
void afisare();
void adauga_arc(int x, int y, int c);

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

void adauga_arc(int x, int y, int c)
{
    G[x][0].c++;
    G[x][G[x][0].c].vf=y;
    G[x][G[x][0].c].c=c;
}

void citire()
{
	int i, j, x, y, cost, m;
	fin>>n>>m;
	x0=1;
	for(i=0;i<m;i++)
	{
		fin>>x>>y>>cost;
		adauga_arc(x, y, cost);
	}
}

int ExtractMin()
{
    int fiu, tata, aux;
    int mn=h[1];
    h[1]=h[lgh--]; poz[h[1]]=-1;
    //downgrade
    tata=1; fiu=2*tata;
    while(fiu<=lgh)
    {
        if(fiu<lgh && dmin[h[fiu]]>dmin[h[fiu+1]]) fiu++;
        if(dmin[h[tata]]>dmin[h[fiu]])
        {
            poz[h[fiu]]=tata; poz[h[tata]]=fiu;
            aux=h[fiu]; h[fiu]=h[tata]; h[tata]=aux;
            tata=fiu; fiu=tata*2;
        }
        else
            break;
    }
    return mn;
}

void InsertHeap(int vf)
{
    h[++lgh]=vf;
    poz[vf]=lgh;
    Upgrade(lgh);
}

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

void dijkstra()
{
	int i, j, vfmin, nrs=1;

	//initializari
	for(i=1;i<=n;i++)
	{
	    dmin[i]=INF; prec[i]=x0; poz[i]=-1;
	}

	//x0 intra in heap
	dmin[x0]=0; prec[x0]=-1; poz[x0]=1; h[1]=x0; lgh=1;

	while(nrs<n) //nu au fost selectate toate vf
	{
	    vfmin=ExtractMin();
	    M[vfmin]=1; nrs++;
	    //parcurg lista de adiacenta a lui vfmin
	    for(j=1;j<=G[vfmin][0].c;j++)
            if(!M[G[vfmin][j].vf]) //nu a fost selectate
                if(dmin[G[vfmin][j].vf]>dmin[vfmin]+G[vfmin][j].c)
                {
                    dmin[G[vfmin][j].vf]=dmin[vfmin]+G[vfmin][j].c;
                    prec[G[vfmin][j].vf]=vfmin;
                    if(poz[G[vfmin][j].vf]==-1)
                        InsertHeap(G[vfmin][j].vf);
                    else
                        Upgrade(poz[G[vfmin][j].vf]); //il promovez
                }
	}
}

void afisare()
{
	int i;
    for(i=2;i<=n;i++)
        fout<<dmin[i]<<' ';
    fout<<'\n';
}