#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

struct lista;

struct elem
{
    int info,info2;
    elem *urm;
    elem()
    {
        info=-1;
        info2=-1;
        urm=NULL;
    }
    ~elem()
    {
        if(urm!=NULL)
            delete urm;
    }
    friend lista;
};

struct lista
{
    elem *urm,*u;
    lista()
    {
        urm=NULL;
        u=NULL;
    }
    ~lista()
    {
        if(urm!=NULL)
            delete urm;
    }
};

void dijkstra(int x,int n,lista *l[50001],int d[50001])
{
    int i,j,k,u,p,c[50001];
    bool v[50001]={0};
    for(i=1;i<=n;i++)
        d[i]=INT_MAX;
    d[x]=0;
    c[0]=x;
    p=u=0;
    while(p<=u)
    {
        int y;
        y=c[p];
        v[y]=1;
        elem *pi;
        for(pi=l[y]->urm;pi!=NULL;pi=pi->urm)
            if(v[pi->info]==0&&d[pi->info]>d[y]+pi->info2)
            {
                d[pi->info]=d[y]+pi->info2;
                if(d[pi->info]>d[c[u]])
                    c[++u]=pi->info;
                else
                {
                    for(j=p;j<u&&pi->info2>=d[c[j]];j++);
                        u++;
                    for(k=u;k>j;k--)
                        c[k]=c[k-1];
                    c[k]=pi->info;
                }
            }

        p++;
    }
    for(i=1;i<=n;i++)
        if(d[i]==INT_MAX)
            d[i]=0;
}

int main()
{
    int n,m,i,d[50001];
    lista *l[50001];
    ifstream f("dijkstra.in");
    f>>n>>m;
    for(i=1;i<=n;i++)
        l[i]=new lista;
    for(i=0;i<m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        elem *p;
        p=new elem;
        p->info=y;
        p->info2=z;
        if(l[x]->u==NULL)
        {
            l[x]->urm=p;
            l[x]->u=p;
        }
        else
        {
            l[x]->u->urm=p;
            l[x]->u=p;
        }
    }
    f.close();
    dijkstra(1,n,l,d);
    ofstream g("dijkstra.out");
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    for(i=1;i<=n;i++)
        delete l[i];
    return 0;
}