#include <bits/stdc++.h>
using namespace std;
int inf=(1<<30);
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int nmax = 50001;
struct graf
{
    int nod,cost;
    graf *next;
};
graf *a[nmax];

int n,m,d[nmax],h[nmax],poz[nmax],k,x,y,z;
void add(int where, int what, int cost)
{
    graf *q=new graf;
    q->nod=what;
    q->cost=cost;
    q->next=a[where];
    a[where]=q;
}
void hswap(int x, int y)
{
    int t=h[x];
    h[x]=h[y];
    h[y]=t;
}
void upheap(int what)
{
    int tata;
    while(what>1)
    {
        tata=(what>>1);
        if(d[h[tata]]>d[h[what]])
        {
            poz[h[what]]=tata;
            poz[h[tata]]=what;
            hswap(tata,what);
            what=tata;
        }
        else what=1;
    }
}
void downheap(int what)
{
    int f;
    while(what<=k)
    {
        f=what;
        if((what<<1)<=k)
        {
            f=what<<1;
            if(f+1<=k)
                if(d[h[f+1]]<d[h[f]])++f;
        }
        else return;
        if(d[h[what]]>d[h[f]])
        {
            poz[h[what]]=f;
            poz[h[f]]=what;
            hswap(what,f);
            what=f;
        }
        else return;
    }
}
void dijkstraheap()
{
    for(int i=2; i<=n; ++i)
    {
        d[i]=inf;
        poz[i]=-1;
    }
    poz[1]=1;
    h[++k]=1;
    while(k)
    {
        int minim=h[1];
        hswap(1,k);
        poz[h[1]]=1;
        --k;
        downheap(1);
        graf *q=a[minim];
        while(q)
        {
            if(d[q->nod]>d[minim]+q->cost)
            {
                d[q->nod]=d[minim]+q->cost;
                if(poz[q->nod]!=-1)
                    upheap(poz[q->nod]);
                else
                {
                    h[++k]=q->nod;
                    poz[h[k]]=k;
                    upheap(k);
                }
            }
            q=q->next;
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        add(x,y,z);
    }
    dijkstraheap();
    for(int i=2;i<=n;i++)
    {
        if(d[i]==inf)g<<0<<" ";
        else g<<d[i]<<" ";
    }
    return 0;
}