#include <algorithm>
#include <fstream>

using namespace std;

const int pinf = 1<<30;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int heap[50005],poz[50005],d[50005];
int n,m,i;

struct nod
{
    int cost,val;
    nod *next;
}*p,*l[50001];

void citire(int &n,int &m)
{
    int x,y,c,i;
    nod *p;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        p=new nod;
        p->val=y;
        p->cost=c;
        p->next=l[x];
        l[x]=p;
    }
}

void urca(int pozi)
{
    while(pozi>1&& d[heap[pozi]]<d[heap[pozi/2]])
    {
        swap(heap[pozi],heap[pozi/2]);
        poz[heap[pozi]]=pozi;
        poz[heap[pozi/2]]=pozi/2;
        pozi/=2;

    }
}

void coboara(int pozi)
{
 {
    int poz1=0;

    while(pozi!=poz1) {
        poz1=pozi;

        if(2*poz1<=n && d[heap[pozi]]>d[heap[2*poz1]])
            pozi=2*poz1;
        if(2*poz1+1<=n && d[heap[pozi]]>d[heap[2*poz1+1]])
            pozi=2*poz1+1;

        swap(heap[pozi],heap[poz1]);
        poz[heap[pozi]]=pozi;
        poz[heap[poz1]]=poz1;

        }
}}


int main()
{
    citire(n,m);
    int ni=n,x;
    for(i=1;i<=n;i++)
    {
        d[i]=pinf;
        heap[i]=poz[i]=i;
    }
    d[1]=0;

    for(i=1;i<=n;i++)
    {
        x=heap[1];
        swap (heap[1],heap[ni]);
        swap (poz[heap[1]],poz[heap[ni]]);
        ni--;
        coboara(1);
        for(p=l[x];p!=NULL;p=p->next)
            if(d[p->val]>d[x]+p->cost)
            {
            d[p->val]=d[x]+p->cost;
            urca(poz[p->val]);
            }
        }

    for(i=2;i<=n;i++)
        if(d[i]==pinf) g<<0<<" ";
    else g<<d[i]<<" ";
    return 0;
}