#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],H[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 i,x,y,z;
    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++)
    if(D[i]!=inf)
    g<<D[i]<<' ';
    else
    g<<0<<' ';

    g<<'\n';
    g.close();
}
//Proceduri Heap

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

void coboara(int nod)
{
    int fiu;
    do
    {
        fiu = 0;
        if(fst(nod)<=HN)
        {
            fiu=fst(nod);
            if(fiu+1<=HN && D[H[fiu+1]]<D[H[fiu]])
            ++fiu;

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

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

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

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

    q=G[S];
    while(q)
    {
        D[q->vecin]=q->cost;
        q=q->link;
    }

    D[S]=0;
    HN=N;
    recreare_heap();
    while(HN)
    {
        nod=H[1];
        minim=D[H[1]];

        H[1]=H[HN];
        --HN;
        coboara(1);

        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;
}