#include <cstdio>
#include <algorithm>
using namespace std;

const int inf=1<<31-1;
int n,h1,d[50001],h[50001],poz[50001];

struct nod
{
    int x,c;
    nod* u;
}*v[50001];

void coboara(int k)
{
    if(k<<1>h1) return;
    int j=k<<1;
    if(j+1<=h1) if(d[h[j+1]]<d[h[j]]) ++j;
    while(d[h[k]]>d[h[j]])
    {
        swap(h[k],h[j]);
        swap(poz[h[k]],poz[h[j]]);
        k=j;
        if(k<<1>h1) return;
        j=k<<1;
        if(j+1<=h1) if(d[h[j+1]]<d[h[j]]) ++j;
    }
}

void urca(int k)
{
    while(k>1&&d[h[k]]<d[h[k>>1]])
    {
        swap(poz[h[k]],poz[h[k>>1]]);
        swap(h[k],h[k>>1]);             //e aceeasi chestie ca si cu swap-urile inversate
        k>>=1;
    }
}

void adauga(int x)
{
    h[++h1]=x;
    poz[x]=h1;
    urca(h1);
}

void update(int k)
{
    if(k>1) if(d[h[k]]<d[h[k>>1]]) {urca(k); return;}
    coboara(k);
}

void sterge(int k)
{
    swap(h[h1],h[k]);
    poz[h[k]]=k;
    poz[h[h1]]=-1;
    --h1;
    update(k);
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,m;
    nod *v1;
    scanf("%d%d",&n,&m);
    for(i=2;i<=n;++i) d[i]=inf;
    while(m)
    {
        --m;
        v1=new nod;
        scanf("%d",&i);
        v1->u=v[i];
        v[i]=v1;
        scanf("%d",&i);
        v1->x=i;
        scanf("%d",&i);
        v1->c=i;
    }
    adauga(1);
    while(h1)
    {
        i=h[1];
        v1=v[i];
        while(v1)
        {
            if(poz[v1->x]!=-1)
            {
                if(poz[v1->x])
                {
                    if(d[v1->x]>d[i]+v1->c)
                    {
                        d[v1->x]=d[i]+v1->c;
                        update(poz[v1->x]);
                    }
                }
                else
                {
                    d[v1->x]=d[i]+v1->c;
                    adauga(v1->x);
                }
            }
            v1=v1->u;
        }
        sterge(1);
    }
    for(i=2;i<=n;++i) printf("%d ",d[i]);
    printf("\n");
    return 0;
}