#include <fstream>
#define nmax 50001
#define tata(x) (x>>1)
#define fst(x) (x<<1)
#define inf 1<<30
using namespace std;

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

graf *G[nmax];
int D[nmax],Hp[nmax];
int N,M,HN;

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

    q->vecin=ce;
    q->cost=cat;
    q->link=G[unde];
    G[unde]=q;
}

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

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

void scrie()
{
    int i;
    ofstream g("dijkstra.out");
    for(i=2;i<=N;i++)
    g<<D[i]<<' ';
    g<<'\n';
}

//Proceduri heap

void interschimba(int &x,int &y)
{
    int z;
    z=x;
    x=y;
    y=z;
}

void coboara(int nod)
{
    int fiu;
    do
    {
        fiu = 0;

        if(fst(nod)<=HN)
        {
            fiu=fst(nod);
            if(fiu+1<=HN && D[Hp[fiu]]>D[Hp[fiu+1]])
              ++fiu;

              if(D[Hp[nod]]>D[Hp[fiu]])
              {
                  interschimba(Hp[nod],Hp[fiu]);
                  nod=fiu;
              }
              else
              fiu=0;
        }
    }while(fiu);
}

int extrage_min()
{
    int x=D[Hp[1]];
    Hp[1]=Hp[HN];
    --HN;
    coboara(1);
    return x;
}

void recreare_heap()
{
    int i;
    for(i=HN/2;i>0;i--)
    coboara(i);
}

void Dijkstra(int start)
{
    int i,minim,ok,nod;
    graf *q;

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

    HN=N;
    ok=1;
    q=G[start];
    while(q)
    {
        D[q->vecin]=q->cost;
        q=q->link;
    }
    D[start]=0;
    D[0]=-1;
    recreare_heap();
    while(ok && HN>0)
    {
        nod=Hp[1];
        minim=extrage_min();

        if(minim==inf)
        ok=0;
        else
        {
            q=G[nod];
            while(q)
            {
                if(D[q->vecin]>D[nod]+q->cost)
                D[q->vecin]=D[nod]+q->cost;
                q=q->link;
            }
            recreare_heap();
        }
    }
}




int main()
{
    citeste();
    Dijkstra(1);
    scrie();
    return 0;
}