#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMAX=200000,inf=1<<30;
int H[NMAX],poz[NMAX],d[NMAX],M,N,k;
struct graf
{
    int vecin,val;
    graf* urm;
}*a[NMAX];
void add(int nod,int vecin,int val)
{
    graf* p=new graf;
    p->urm=a[nod];
    p->vecin=vecin;
    p->val=val;
    a[nod]=p;
}
void schimbare(int n,int m)
{
    swap(H[n],H[m]);
    swap(poz[H[n]],poz[H[m]]);
}
void upheap(int k)
{
    while(d[H[k]]<d[H[k/2]] && k>1)
    {
        schimbare(k,k/2);
        k/=2;
    }
}
void downheap(int v)
{
    int ok=1;
    int st=v*2,dr=v*2+1;
    while(v<=k/2 && ok==1)
    {
        ok=0;
        if(dr<=k && d[H[dr]]<d[H[st]] &&d[H[v]]>d[H[dr]])
            {
                schimbare(v,dr);
                v=dr;
                ok=1;
            }
        else if(d[H[st]]<d[H[v]] && st<=k)
             {
                 schimbare(st,v);
                 v=st;
                 ok=1;
             }
        st=v*2;dr=v*2+1;
    }
}
void dijkstra()
{
    for(int i=2;i<=N;++i)
        d[i]=inf,poz[i]=-1;
    H[++k]=1;
    poz[1]=1;
    while(k)
    {
        int min=H[1];
        swap(H[1],H[k]);
        poz[H[1]]=1;
        --k;
        downheap(1);
        graf* p=a[min];
        while(p)
        {
            if(d[p->vecin]>d[min]+p->val)
            {   d[p->vecin]=d[min]+p->val;
                if(poz[p->vecin]!=-1)
                    upheap(poz[p->vecin]);
                else
                    {
                        H[++k]=p->vecin;
                        poz[H[k]]=k;
                        upheap(k);
                    }
            }
            p=p->urm;
        }
    }
}
int main()
{
    fin>>N>>M;
    int x,y,z;
    while(M--)
    {
        fin>>x>>y>>z;
        add(x,y,z);
    }
    dijkstra();
    for(int i=2;i<=N;++i)
        if(d[i]!=inf) fout<<d[i]<<" ";
        else fout<<0<<" ";
    return 0;
}