#include <cstdio>

using namespace std;

struct p1
{
    int nod1,nod2,cost;
    int urm;
}muchii[250001];

int heap[250001],h_nr,d[50001],viz[50001];
int in[50001],sf[50001];

void schimb(int &a,int &b)
{
    int z=a;
    a=b;
    b=z;
}

void up(int x)
{
    while (muchii[heap[x/2]].cost>muchii[heap[x]].cost && x!=1)
    {
        schimb(heap[x/2],heap[x]);
        x=x/2;
    }
}

void down(int x)
{
    if (x*2==h_nr)
    {
        if (muchii[heap[x*2]].cost<muchii[heap[x]].cost)
            schimb(heap[x*2],heap[x]);
    }
    else
    {
        if (h_nr>x*2)
        {
            int min1=muchii[heap[x*2]].cost,poz=x*2;
            if (min1>muchii[heap[x*2+1]].cost)
            {
                poz=x*2+1;
                min1=muchii[heap[x*2+1]].cost;
            }
            if (min1<muchii[heap[x]].cost)
            {
                schimb(heap[poz],heap[x]);
                down(poz);
            }
        }
    }
}

void afiseaza_muchii(int x)
{
    int o=in[x];
    while (muchii[o].urm)
    {
        printf("%d %d\n",muchii[o].nod1,muchii[o].nod2);
        o=muchii[o].urm;
    }
    if (in[x]!=0)
    printf("%d %d",muchii[o].nod1,muchii[o].nod2);
}

void adauga_muchii(int x)
{
    int o=in[x];
    while (muchii[o].urm)
    {
        h_nr++;
        heap[h_nr]=o;
        up(h_nr);
        o=muchii[o].urm;
    }
    if (in[x]!=0)
    {
        h_nr++;
        heap[h_nr]=o;
        up(h_nr);
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m;
    int INF=(1<<31)-1;
    scanf("%d %d",&n,&m);
    for (int i=2;i<=n;i++)
        d[i]=INF;
    for (int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d %d %d\n",&a,&b,&c);
        if (in[a]==0)
        {
            in[a]=i;
            sf[a]=i;
        }
        else
        {
            muchii[sf[a]].urm=i;
            sf[a]=i;
        }
        muchii[i].nod1=a;
        muchii[i].nod2=b;
        muchii[i].cost=c;
        if (muchii[i].nod1==1)
        {
            h_nr++;
            heap[h_nr]=i;
            up(h_nr);
        }
    }
    d[1]=0;
    for (int i=1;h_nr;i++)
    {
        int y=muchii[heap[1]].nod2;
        if (d[y]>muchii[heap[1]].cost+d[muchii[heap[1]].nod1])
        {
            d[muchii[heap[1]].nod2]=muchii[heap[1]].cost+d[muchii[heap[1]].nod1];
            heap[1]=heap[h_nr];
            h_nr--;
            down(1);
            adauga_muchii(y);
        }
        else
        {
            heap[1]=heap[h_nr];
            h_nr--;
            down(1);
        }
    }
    for (int i=2;i<=n;i++)
        if (d[i]==INF) printf("0 ");
        else printf("%d ",d[i]);

}