#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct ele{
int x,y,c;};
int P[50002],heap[50002],P_noduri[50002],n,dim;
//struct ele c[250002];
void schimba_pozitiile_in_heap(int a,int b)
{
    int sw;
    sw = P[b];
    P[b]=P[a];
    P[a] = sw;
}
/*int gasit2(int a,int b,int p,int q)
{
    int mij=(p+q)/2;
    if(q<p)
        return -1;
    else
    {
        if(b==c[mij].y)
            return c[mij].c;
        else
            if(b<c[mij].y)
                return gasit2(a,b,p,mij-1);
            else
                return gasit2(a,b,mij+1,q);
    }
}
int gasit1(int a,int b,int p,int q,int dim2)
{
    int i,j,mij =(p+q)/2;
    if(q<p)
        return -1;
    else
    {
        if (c[mij].x==a)
        {
            i = mij;
            j = mij;
            while(c[i].x==a && i>0)
                i--;
            while(c[j].x==a && j<=dim2)
                j++;
            if(i>0 && c[i].x!=a)
                i++;
            if(j<=dim2 && c[j].x!=a)
                j--;
            if(i==0)
                i++;
            if(j==dim2+1)
                j--;
            return gasit2(a,b,i,j);
        }
        else
            if(a<c[mij].x)
                return gasit1(a,b,p,mij-1,dim2);
            else
                return gasit1(a,b,mij+1,q,dim2);
    }
}
bool comp(struct ele a,struct ele b)
{
    if (a.x==b.x)
        if (a.y<=b.y)
            return true;
        else
             return false;
    else
        if (a.x<b.x)
            return true;
        else
            return false;
}*/
int main()
{
    int m,i,x,y,cost,start,poz,sch1,sch2,nodu,val,j;
    in>>n>>m;
    bool viz[n+1];
    int c[n+1][n+1];
    bool see[n+1][n+1];
    int d[n+1],noduri[n+1],no_siz=1;
    for(i=1;i<=n;i++)
    {
        d[i]=1<<30;
        viz[i]=false;
        for(j=1;j<=n;j++)
            see[i][j]=false;
    }
    noduri[1]=1;
    heap[1]=1;
    P[1]=1;
    P_noduri[1]=1;
    viz[1]=true;
    vector<int> v[n+1];
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>cost;
        if (!viz[x])
        {
            viz[x]=true;
            no_siz++;
            heap[no_siz] = noduri[no_siz]=x;
            P[x]=no_siz;
            P_noduri[x]=no_siz;
        }
        if(!viz[y])
        {
            no_siz++;
            viz[y]=true;
            heap[no_siz] = noduri[no_siz]=y;
            P[y]=no_siz;
            P_noduri[y]=no_siz;
        }
        c[x][y]=cost;
        see[x][y]=true;
        v[x].push_back(y);
    }
    d[1]=0;
    while(no_siz>0)
    {
        start = heap[1];//extragem nodul cu distanta min di heap adica primul
        poz=1;
        dim = no_siz;
        if (P_noduri[heap[1]]!=no_siz)
        {
            sch1 = P_noduri[heap[1]];
            sch2 = noduri[no_siz];
            nodu = heap[1];
            swap(noduri[P_noduri[heap[1]]],noduri[no_siz]);
            P_noduri[nodu]=P_noduri[sch2];
            P_noduri[sch2]=sch1;
            no_siz--;
        }
        else
            no_siz--;
        schimba_pozitiile_in_heap(heap[dim],heap[1]);
        swap(heap[1],heap[dim]);
        dim--;
        while((2*poz<=dim || 2*poz+1<=dim)&&(d[heap[poz]]>d[heap[2*poz]] || d[heap[poz]]>d[heap[2*poz+1]]))
        {
            if(2*poz<=dim && 2*poz+1<=dim)
                if(d[heap[2*poz]]<d[heap[2*poz+1]])
                 {
                     schimba_pozitiile_in_heap(heap[2*poz],heap[poz]);
                     swap(heap[2*poz],heap[poz]);
                     poz *=2;
                 }
                else
                {
                     schimba_pozitiile_in_heap(heap[2*poz+1],heap[poz]);
                     swap(heap[2*poz+1],heap[poz]);
                     poz = 2*poz+1;
                }
            else
                if(2*poz<=dim)
                {
                    schimba_pozitiile_in_heap(heap[2*poz],heap[poz]);
                    swap(heap[2*poz],heap[poz]);
                    poz *=2;
                }
                else
                {
                    schimba_pozitiile_in_heap(heap[2*poz+1],heap[poz]);
                    swap(heap[2*poz+1],heap[poz]);
                    poz = 2*poz+1;
                }
        }
        for(i=1;i<=no_siz;i++)
            if(see[start][noduri[i]])
                if ( (c[start][noduri[i]]+d[start]<d[noduri[i]]) || (d[noduri[i]]==1<<30) )
                {
                    d[noduri[i]] = see[start][noduri[i]]+d[start];
                    poz = P[noduri[i]];
                    while((poz/2) && ( d[heap[poz]]<d[heap[poz/2]] || d[heap[poz/2]]==1<<30))
                    {
                        schimba_pozitiile_in_heap(heap[poz],heap[poz/2]);
                        swap(heap[poz],heap[poz/2]);
                        poz /=2;
                    }
                }
    }
    for(i=2;i<=n;i++)
        if (d[i]==1<<30)
            d[i] = 0;
    for(i=2;i<=n;i++)
        out<<d[i]<<" ";
    return 0;
}