#include <cstdio>
#include <algorithm>
#include <cmath>
#define NMAX 50005

using namespace std;

struct node
{
    int x,c;
};
vector<node>v[NMAX];
int n,m,i,j,x,y,c,lg;
int d[NMAX],Poz[NMAX],H[NMAX*2];
node pp(int a,int b)
{
    node X;X.x=a;X.c=b;
    return X;
}

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

void bagaheap(int nod)
{
    ++lg;
    H[lg]=nod;
    Poz[nod]=lg;
    urca(lg);
}

void coboara(int poz)
{
    while((poz*2 <= lg && d[H[poz]] > d[H[poz*2]]) || (poz*2+1 <=lg && d[H[poz]] > d[H[poz*2+1]]))
    {
        if(poz*2+1 > lg || (d[H[poz*2]] < d[H[poz*2+1]]))
        {
            swap(H[poz],H[poz*2]);
            swap(Poz[H[poz]],Poz[H[poz*2]]);
            poz=poz*2;
        }
        else
        {
            swap(H[poz],H[poz*2+1]);
            swap(Poz[H[poz]],Poz[H[poz*2+1]]);
            poz=poz*2+1;
        }
    }
}

int Minim()
{
    int x=H[1];
    swap(H[1],H[lg]);
    swap(Poz[1],Poz[lg]);
    --lg;
    coboara(1);
    Poz[x]=0;
    return x;
}


int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(pp(y,c));
    }
    d[1]=0;Poz[1]=1;
    bagaheap(1);
    for(i=2;i<=n;++i)
    {
        Poz[i]=0;d[i]=INFINITY;
    }
    while(lg > 0)
    {
        int x= Minim();
        for(i=0;i<v[x].size();++i)
        {
            int c=v[x][i].c;
            y=v[x][i].x;
            if(d[x] + c < d[y])
            {
                d[y]=d[x]+c;
                if(Poz[y] == 0) bagaheap(y);
                    else urca(Poz[y]);
            }
        }
    }

    for(i=2;i<=n;++i)
        if(d[i] == INFINITY) printf("0 ");
            else printf("%d ",d[i]);
    return 0;
}