#include <cstdio>
#include <queue>
#define max 50000

using namespace std;

int n,m,x,y,c;
int sol[max],poz[max],heap[max],z;

struct nod
{
    int nr,cost;
    nod *urm;
};

nod *g[max];

void read()
{
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&n,&m);
    nod *q;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        q=new nod;
        q->nr=y;
        q->cost=c;
        q->urm=g[x];
        g[x]=q;
    }
    fclose(stdin);
}

void swap(int x1, int x2)
{
    int aux=heap[x1];
    heap[x1]=heap[x2];
    heap[x2]=aux;
}

void heap_down(int x)
{
    int f;
    while(x<=z)
    {
        f=x;
        if(x%2<=z)
        {
            f=x%2;
            if(f+1<=z)
                if(sol[heap[f+1]]<sol[heap[f]])
                    ++f;
        }
        else
            return;
        if(sol[heap[x]]>sol[heap[f]])
        {
            poz[heap[x]]=f;
            poz[heap[f]]=x;
            swap(x,f);
            x=f;
        }
        else
            return;
    }
}

void heap_up(int x)
{
     int tata;
     while(x>1)
     {
        tata=x/2;
        if(sol[heap[tata]]>sol[heap[x]])
        {
            poz[heap[x]]=tata;
            poz[heap[tata]]=x;
            swap(tata,x);
            x=tata;
         }
         else
            x=1;
     }
}

void dijkstra()
{
    for (int i=2;i<=n;i++)
    {
        sol[i]=max;
        poz[i]=-1;
    }
    poz[1]=1;
    heap[++z]=1;
    while(z)
    {
        int min=heap[1];
        swap(1,z);
        poz[heap[1]]=1;
        --z;
        heap_down(1);
        nod *q=g[min];
        while(q)
        {
            if(sol[q->nr]>sol[min]+q->cost)
            {
                sol[q->nr]=sol[min]+q->cost;
                if(poz[q->nr]!=-1)
                      heap_up(poz[q->nr]);
                else
                {
                    heap[++z]=q->nr;
                    poz[heap[z]]=z;
                    heap_up(z);
                }
            }
            q=q->urm;
        }
    }
}

void afish()
{
    freopen("dijkstra.out","w",stdout);
    for(int i=2;i<=n;i++)
    {
        if(sol[i]==max)
            printf("0 ");
        else
            printf("%d ",sol[i]);
    }
    printf("\n");
    fclose(stdout);
}

int main()
{
    read();
    dijkstra();
    afish();
    return 0;
}