#include<cstdio>
#include<vector>

using namespace std;

vector<int> con[50010],cost[50010];
int n,m,x,y,l;
int sz,hppos[50010],vec[50010];
int val[50010];

void setup(int pos)
{
    while(val[hppos[pos]]<val[hppos[pos/2]]&&pos>1)
    {
        swap(hppos[pos],hppos[pos/2]);
        swap(vec[hppos[pos]],vec[hppos[pos/2]]);
        pos/=2;
    }
}
void setdown(int pos)
{
    while((pos*2)<=sz)
    {
        if((pos*2)+1<=sz)
        {
            if(val[hppos[pos*2]]<val[hppos[(pos*2)+1]])
            {
                if(val[hppos[pos]]>val[hppos[pos*2]])
                {
                    swap(hppos[pos],hppos[pos*2]);
                    swap(vec[hppos[pos]],vec[hppos[pos*2]]);
                    pos*=2;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if(val[hppos[pos]]>val[hppos[(pos*2)+1]])
                {
                    swap(hppos[pos],hppos[(pos*2)+1]);
                    swap(vec[hppos[pos]],vec[hppos[(pos*2)+1]]);
                    pos*=2;
                    pos++;
                }
                else
                {
                    break;
                }
            }
        }
        else
        {
            if(val[hppos[pos]]>val[hppos[pos*2]])
            {
                swap(hppos[pos],hppos[pos*2]);
                swap(vec[hppos[pos]],vec[hppos[pos*2]]);
                pos*=2;
            }
            else
            {
                break;
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    for(int i=1;i<50001;i++)
    {
        val[i]=250000001;
    }

    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&l);
        con[x].push_back(y);
        cost[x].push_back(l);
    }
    sz=1;
    hppos[1]=1;
    vec[1]=1;
    val[1]=0;
    while(sz>0)
    {
        int next;
        int cst;
       // printf("%d\n",hppos[1]);
        while(!con[hppos[1]].empty())
        {
            next=con[hppos[1]].back();
            cst=cost[hppos[1]].back();
            if(val[next]!=250000001)
            {
                val[next]=min(val[next],val[hppos[1]]+cst);
                if(vec[next]!=0)
                {
                    setup(vec[next]);
                }
            }
            else
            {
                val[next]=val[hppos[1]]+cst;
                sz++;
                vec[next]=sz;
                hppos[sz]=next;
                setup(vec[next]);
            }
            con[hppos[1]].pop_back();
            cost[hppos[1]].pop_back();
        }
       // for(int i=1;i<=sz;i++) printf("%d ",hppos[i]);
       // printf("\n");
        vec[hppos[1]]=0;
        swap(hppos[1],hppos[sz]);
        sz--;
        setdown(1);
       // for(int i=1;i<=sz;i++) printf("%d ",hppos[i]);
       // break;
    }

    for(int i=2;i<=n;i++)
    {
        if(val[i]==250000001)
        {
             printf("0 ");
        }
        else
        {
            printf("%d ",val[i]);
        }
    }
}