#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(hppos[pos*2]<hppos[(pos*2)+1])
            {
                if(hppos[pos]>hppos[pos*2])
                {
                    swap(hppos[pos],hppos[pos*2]);
                    swap(vec[hppos[pos]],vec[hppos[pos*2]]);
                    pos*=2;
                }
                else if(hppos[pos]>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(hppos[pos]>hppos[(pos*2)+1])
                {
                    swap(hppos[pos],hppos[(pos*2)+1]);
                    swap(vec[hppos[pos]],vec[hppos[(pos*2)+1]]);
                    pos*=2;
                    pos++;
                }
                else if(hppos[pos]>hppos[pos*2])
                {
                    swap(hppos[pos],hppos[pos*2]);
                    swap(vec[hppos[pos]],vec[hppos[pos*2]]);
                    pos*=2;
                }
                else
                {
                    break;
                }
            }
        }
        else
        {
            if(hppos[pos]>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)
    {
        vector<int>::iterator it2=cost[hppos[1]].begin();
        for(vector<int>::iterator it=con[hppos[1]].begin();it!=con[hppos[1]].end();it++)
        {
            sz++;
            hppos[sz]=*it;
            if(val[hppos[sz]]==250000001)
            {
                val[hppos[sz]]=val[hppos[1]]+*it2;
                vec[hppos[sz]]=sz;
                setup(sz);
            }
            else
            {
                val[hppos[sz]]=min(val[hppos[sz]],val[hppos[1]]+*it2);
                setup(vec[hppos[sz]]);
                sz--;
            }
            it2++;
        }
        swap(hppos[1],hppos[sz]);
        sz--;
        setdown(1);
    }

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