#include <fstream>
#include <iostream>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct lista
{
    int y,c;
    lista *urm;
} *g[50010];
int n,m,nh,inf=2000000000,h[50010],d[50010],poz[50010];

void heapup (int nod)
{
    int hnod=h[nod],cd=d[h[nod]];
    while (nod>1&&cd<d[h[nod/2]])
    {
        h[nod]=h[nod/2];
        poz[h[nod]]=nod;
        nod/=2;
    }
    h[nod]=hnod;
    poz[hnod]=nod;
}

void heapdown (int nod)
{
    int st,dr,i,hnod=h[nod],cd=d[h[nod]];
    while (nod<=nh)
    {
        st=2*nod;
        if (st<=nh)
        {
            dr=st+1;
            if (dr<=nh)
            {
                if (d[h[st]]<d[h[dr]])
                    i=st;
                else
                    i=dr;
            }
            else
                i=st;
            if (d[h[i]]<cd)
            {
                poz[h[i]]=nod;
                h[nod]=h[i];
                nod=i;
            }
            else
                break;
        }
        else
            break;
    }
    h[nod]=hnod;
    poz[hnod]=nod;
}

int extragemin ()
{
    int nod=h[1];
    h[1]=h[nh];
    poz[h[1]]=1;
    nh--;
    heapdown (1);
    return nod;
}
void dijkstra (int sursa)
{
    int i,nod;
    lista *p;
    for (i=1;i<=n;i++)
    {
        d[i]=inf;
        h[i]=i;
        poz[i]=i;
    }
    d[sursa]=0;
    h[sursa]=1;
    poz[1]=sursa;
    h[1]=sursa;
    poz[sursa]=1;
    nh=n;
    while (nh)
    {
        nod=extragemin();
        for (p=g[nod];p;p=p->urm)
        {
            if (d[p->y]>d[nod]+p->c)
            {
                d[p->y]=d[nod]+p->c;
                heapup (poz[p->y]);
            }
        }
    }
}

int main()
{
    int i,x,y,c;
    lista *p;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        p=new lista;
        p->urm=g[x];
        p->y=y;
        p->c=c;
        g[x]=p;
    }
    dijkstra (1);
    for (i=2;i<=n;i++)
    {
        if (d[i]==inf)
            fout<<0<<' ';
        else
            fout<<d[i]<<' ';
    }
    fout<<'\n';
    fin.close ();
    fout.close ();
    return 0;
}