#include<cstdio>
#include<vector>

using namespace std;

int n,m;
vector< pair<int,int> > adj[50010];
int heap[50010],sz;
int res[50010];
int pos_in_heap[50010];
bool viz[50010];

void up_heap(int nod)
{
    while(res[heap[nod/2]]>res[heap[nod]]&&nod>1)
    {
        swap(heap[nod/2],heap[nod]);
        swap(pos_in_heap[nod],pos_in_heap[nod/2]);
        up_heap(nod/2);
    }
}

void down_heap(int nod)
{
    while(nod*2<=sz)
    {
        if(nod*2+1<=sz)
        {
            if(res[heap[nod*2]]<res[heap[nod*2+1]])
            {
                if(res[heap[nod]]>res[heap[nod*2]])
                {
                    swap(heap[nod],heap[nod*2]);
                    swap(pos_in_heap[nod*2],pos_in_heap[nod]);
                    down_heap(nod*2);
                }
                else
                {
                    break;
                }
            }
            else
            {
                if(res[heap[nod]]>res[heap[nod*2+1]])
                {
                    swap(heap[nod],heap[nod*2+1]);
                    swap(pos_in_heap[nod*2+1],pos_in_heap[nod]);
                    down_heap(nod*2+1);
                }
                else
                {
                    break;
                }
            }
        }
        else if(res[heap[nod]]>res[heap[nod*2]])
        {
            swap(heap[nod],heap[nod*2]);
            swap(pos_in_heap[nod*2],pos_in_heap[nod]);
            down_heap(nod*2);
        }
        else
        {
            break;
        }
    }
}

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

    scanf("%d %d",&n,&m);

    sz=1;
    pos_in_heap[1]=1;
    heap[1]=1;
    res[1]=0;
    for(int i=2;i<=n;i++)
    {
        res[i]=1000000001;
    }

    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        pair<int,int> val(y,c);
        adj[x].push_back(val);
    }
    //int lg=2;
    while(sz>0)
    {
        //printf("***\n");
        viz[heap[1]]=1;
        for(vector< pair<int,int> >::iterator it=adj[heap[1]].begin();it!=adj[heap[1]].end();++it)
        {
            //printf("%d %d %d\n",heap[1],(*it).first,(*it).second);
            if(viz[(*it).first]==0)
            {
                viz[(*it).first]=1;
                sz++;
                heap[sz]=(*it).first;
                pos_in_heap[(*it).first]=sz;
                res[(*it).first]=res[heap[1]]+(*it).second;
                up_heap(pos_in_heap[(*it).first]);
            }
            else if(res[(*it).first]>res[heap[1]]+(*it).second)
            {
                res[(*it).first]=res[heap[1]]+(*it).second;
                up_heap(pos_in_heap[(*it).first]);
            }
            /*lg=1;
            for(int i=1;i<=sz;i++)
            {
                if(i==lg)
                {
                    lg<<=1;
                    printf("\n");
                }
                printf("%d ",res[heap[i]]);
            }
            printf("\n");*/
        }
        //printf("\n");
        pos_in_heap[heap[sz]]=1;
        swap(heap[1],heap[sz]);
        sz--;
        down_heap(1);
    }
    for(int i=2;i<=n;i++)
    {
        if(res[i]==1000000001)
        {
            printf("0 ");
        }
        else
        {
            printf("%d ",res[i]);
        }
    }
}