#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],P[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=Hp[x];
    Hp[x]=Hp[y];
    Hp[y]=z;

    z=P[Hp[x]];
    P[Hp[x]]=P[Hp[y]];
    P[Hp[y]]=z;
}

void infiltreaza(int nod)
{
    if(D[Hp[nod]]>D[Hp[tata(nod)]])
    return;
    interschimba(nod,tata(nod));
    infiltreaza(tata(nod));
}
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(nod,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]=P[i]=i;
        D[i]=inf;
    }

    HN=N;

    Hp[1]=start;
    Hp[start]=1;

    D[start]=0;
    D[0]=-1;
    for(i=1;i<=N;i++)
    {
        nod=Hp[1];
        Hp[1]=Hp[HN];
        --HN;
        coboara(1);

        q=G[nod];
            while(q)
            {
                if(D[q->vecin]>D[nod]+q->cost)
                {
                    D[q->vecin]=D[nod]+q->cost;
                    infiltreaza(q->vecin);
                }
                q=q->link;
            }
        }
}




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