#include <iostream>
#include <cstdio>
#include <vector>
#define inf 200050

using namespace std;

vector< vector< pair<int,int> > >g(50050);
int poz[50050];
int dist[50050];
int heap[50050];
int n,k;

void down_heap(int node)
{
    int son=0;
    if(2*node+1<=n && dist[heap[node]]>dist[heap[2*node+1]])
        son=2*node+1;
    if(2*node<=n && dist[heap[node]]>dist[heap[2*node]] && dist[heap[son]]>dist[heap[2*node]])
        son=2*node;
    if(son!=0)
    {
        swap(heap[node],heap[son]);
        swap(poz[heap[node]],poz[heap[son]]);
        down_heap(son);
    }
}

void up_heap(int node)
{
    if(node==1)
        return;
    int dad=node/2;
    if(dist[heap[node]]>dist[heap[dad]])
    {
        swap(heap[node],heap[dad]);
        swap(poz[heap[node]],poz[heap[dad]]);
        up_heap(dad);
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int m,x,y,c,i,node;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
    }
    for(i=0;i<=n;i++)
    {
        poz[i]=-1;
        dist[i]=inf;
    }
    dist[1]=0;
    heap[++k]=1;

    while(k!=0)
    {
        node=heap[1];
        poz[heap[1]]=1;
        heap[1]=0;
        swap(heap[1],heap[k]);
        down_heap(1);
        k--;
        for(i=0;i<g[node].size();i++)
        {
            if(dist[g[node][i].first]>dist[node]+g[node][i].second)
            {
                dist[g[node][i].first]=dist[node]+g[node][i].second;
                if(poz[g[node][i].first]!=-1)
                     up_heap(poz[g[node][i].first]);
                else
                {
                    k++;
                    poz[g[node][i].first]=k;
                    heap[k]=g[node][i].first;
                    up_heap(k);
                }
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(dist[i]!=inf)
            printf("%d ",dist[i]);
        else
            printf("0 ");
    }
    return 0;
}