#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod{int nr; int cost; nod *urm;}*p;

nod *L[50000];
int n,m,x,y,cs,i,k,s,kk,j;
int viz[50000],inainte[50000],c[50000];

void adauga(int x, int y, int cs)
{
    p = new nod;
    p->nr = y;
    p->cost = cs;
    p->urm = L[x];
    L[x] = p;
}

void citireGraf()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>cs;
        adauga(x, y, cs);
        adauga(y, x, cs);
    }
}

void primaFaza()
{
    viz[1]=1;
    p=L[1];
    while(p)
    {
        i=p->nr;
        c[i]=p->cost;
        inainte[i]=1;
        p=p->urm;
    }
}

void alegemK()
{
    int minim = 10001;
    for(int k=1;k<=m;++k)
        if(viz[k]==0 && c[k]!=0 && c[k]<minim) minim = c[k], kk=k;
    viz[k]=1;
}

void drum(int v)
{
    if(v!=0)
    {
        drum(inainte[v]);
        g<<v<<' ';
    }
}
void afisamToateChestiile()
{
    int i=0;
    g<<"\nAFISARI"<<' '<<k<<'\n';
    g<<"viz:";
    for(i=1;i<=n;++i)
        g<<viz[i]<<' ';
    g<<'\n';
    g<<"inainte:";
    for(i=1;i<=n;++i)
        g<<inainte[i]<<' ';
    g<<'\n';
    g<<"c:";
    for(i=1;i<=n;++i)
        g<<c[i]<<' ';
    g<<'\n';
}

int main()
{
    citireGraf();
    primaFaza();
    for(i=1;i<=n-1;++i)
    {
        alegemK();
        k=kk;
        p=L[k];
        while(p)
        {
            if(viz[p->nr]==0)
            {
                j=p->nr;
                inainte[j]=k;
            }
            p=p->urm;
        }
        p=L[k];
        while(p)
        {
            j=p->nr;
            if(viz[j]==0)
            {
                if(c[j]>c[k]+p->cost || c[j]==0)
                {
                 c[j]=c[k]+p->cost;
                 inainte[j]=k;
                }

            }
            p=p->urm;
           // afisamToateChestiile();
        }

    }
    for(int i=2;i<=n;++i)
    {
        g<<c[i]<<' ';

    }
    f.close();g.close();
    return 0;
}