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

struct graf
{
    int nod,cost;
    graf *next;
}*a[50005];

int n,m,d[50005],h[50005],poz[50005],k,x,y,z,i;
const int inf=1<<30;

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 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;
            swap(h[tata],h[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;

            swap(h[what],h[f]);

            what=f;
        }
        else
        {
            return;
        }
    }
}

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

    h[++k]=1;

    while(k)
    {
        minn=h[1];
        swap(h[1],h[k]);
        poz[h[1]]=1;
        --k;

        downheap(1);

        graf *q=a[minn];

        while(q)
        {
            if(d[q->nod]>d[minn] + q->cost)
            {
                d[q->nod]=d[minn] + 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()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        add(x,y,z);
    }
    dijkstra_heap();
    for(i=2;i<=n;i++)
    {
        if(d[i]==inf)
        {
            fout<<"0"<<" ";
        }
        else
        {
            fout<<d[i]<<" ";
        }
    }
    return 0;
}