#include <fstream>
#define maxn 50005
#define inf 200002
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int n,poz[maxn],d[maxn],h[maxn],m,k;

struct graf
{
    int nod,cost;
    graf *next;
};
graf *v[maxn];

void add(int WHERE, int WHAT,int cost)
{
    graf *p=new graf;
    p -> nod=WHAT;
    p -> cost=cost;
    p -> next=v[WHERE];
    v[WHERE]=p;
}
void swapp(int i, int j)
{
    int t;
    t=h[i];
    h[i]=h[j];
    h[j]=t;
}
void citire()
{
    int x,y,z;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
    }
}

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;

            swapp(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;

            swapp(what, f);

            what = f;
        }
        else
            return;
    }
}

void dijkstra()
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        d[i]=inf;
        poz[i]=-1;
    }

    poz[1]=1;
    h[++k]=1;
    while(k)
    {
        int minv=h[1];
        swapp(1,k);
        poz[h[i]]=1;
        k--;

        downheap(1);
        graf *q=v[minv];
        while(q)
        {
            if(d[q->nod]>d[minv]+q->cost)
            {
                d[q->nod]=d[minv]+q->cost;
                if(poz[q->nod]!=-1)
                    upheap(poz[q->nod]);
                else
                {
                    h[++k]=q->nod;
                    poz[q->nod]=k;
                    upheap(k);
                }

            }
            q=q->next;
        }
    }
}
int main()
{
    citire();
    dijkstra();
    for(int i=2;i<=n;i++)
        if(d[i]!=inf)
            cout<<d[i]<<" ";
        else
            cout<<0<<" ";
    return 0;
}