#include<fstream>
#define nmax 50001
#define inf 0x3f3f3f3f
using namespace std;

struct nod_lista{
    int vecin,cost;
    nod_lista *link;
};

nod_lista *G[nmax],*Last[nmax];
int D[nmax],Frunza[nmax],HP[nmax];
int N,M,nHP;

void adauga(int unde,int ce,int cat)
{
    nod_lista *q=new nod_lista;

    q->vecin=ce;
    q->cost=cat;
    q->link=NULL;
    if(!G[unde])
    G[unde]=Last[unde]=q;
    else
    {
        Last[unde]->link=q;
        Last[unde]=q;
    }
}

void citeste()
{
    ifstream f("dijkstra.in");
    int x,y,z,i;

    f>>N>>M;

    for(i=1;i<=M;i++)
    {
        f>>x>>y>>z;
        adauga(x,y,z);
    }

    f.close();
}

//Proceduri heap

void interschimba(int frunza1,int frunza2)
{
    int aux;
    aux=HP[frunza1];
    HP[frunza1]=HP[frunza2];
    HP[frunza2]=aux;

    aux=Frunza[HP[frunza1]];
    Frunza[HP[frunza1]]=Frunza[HP[frunza2]];
    Frunza[HP[frunza2]]=aux;
}


void coboara(int frunza)
{
    int fiu;
    do
    {
        fiu = 0;
        if(2*frunza<=nHP)
        {
            fiu=2*frunza;
            if(fiu+1<=nHP && D[HP[fiu+1]]<D[HP[fiu]])
            ++fiu;

            if(D[HP[frunza]]>D[HP[fiu]])
            {
                interschimba(frunza,fiu);
                frunza=fiu;
            }
            else

            fiu = 0;
        }
    }while(fiu);
}

void infiltrare(int frunza)
{
    if(frunza>1)
       if(D[HP[frunza]]>D[HP[frunza/2]])
         return;
      else
      {interschimba(frunza,frunza/2);
          infiltrare(frunza/2);
          }
}





void Dijkstra(int S)
{
    nod_lista *q;

    int nodmin,i;

    for(i=1;i<=N;i++)
    {
        D[i]=inf;
        HP[i]=Frunza[i]=i;
    }

    nHP=N;
    D[S]=0;
    D[0]=-1;
    interschimba(1,S);

    for(i=1;i<=N;i++)
    {
        nodmin=HP[1];
        HP[1]=HP[nHP];
        --nHP;
        coboara(1);

        q=G[nodmin];

        while(q)
        {
            if(D[q->vecin]>D[nodmin]+q->cost)
            {
                D[q->vecin]=D[nodmin]+q->cost;
                infiltrare(Frunza[q->vecin]);
            }
            q=q->link;
        }
    }
}

void rezolva()
{
    Dijkstra(1);
}

void scrie()
{
    int i;
    ofstream g("dijkstra.out");

    for(i=2;i<=N;i++)
    if(D[i]==inf)
    g<<0<<' ';
    else
    g<<D[i]<<' ';

    g<<'\n';
    g.close();
}

int main()
{
    citeste();
    rezolva();
    scrie();
    return 0;
}