//dijkstra cu heap

#include <cstdio>
#define max 50001

using namespace std;

struct nod {int inf,cost; nod *urm;} *g[max];
int n,m,z;
int poz[max],heap[max],sol[max];

void swap(int x, int y)
{
    int aux=heap[x];
    heap[x]=heap[y];
    heap[y]=aux;
}

void baga(int x, int y, int z)
{
    nod *q=new nod;
    q->inf=y;
    q->cost=z;
    q->urm=g[x];
    g[x]=q;
}

void heap_down(int x)
{
    int f;
    while(x<=z)
    {
        f=x;
        if(2*x<=z)
        {
            f=2*x;
            if(f+1<=z)
                if(sol[heap[f+1]]<sol[heap[f]])
                    f++;
        }
        else
            return;
        if(sol[heap[f]]<sol[heap[x]])
        {
            poz[heap[f]]=x;
            poz[heap[x]]=f;
            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[tata]]=x;
            poz[heap[x]]=tata;
            swap(tata,x);
            x=tata;
        }
        else
            return;
    }
}

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

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        baga(x,y,z);
    }
    dijkstra();
    for(int i=2;i<=n;i++)
        printf("%d ",sol[i]);
    fclose(stdout);
    return 0;
}