#include<cstdio>
#include<vector>

using namespace std;

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

void up_heap(int nod)
{
    if(nod!=1)
    {
        if(res[heap[nod/2]]>res[heap[nod]])
        {
            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)
{
    if(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
            {
                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 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);
        }
    }
}

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

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

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

    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);
    }

    while(sz>0)
    {
        //printf("***\n");
        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(res[(*it).first]>res[heap[1]]+(*it).second)
            {
                res[(*it).first]=res[heap[1]]+(*it).second;
                up_heap(pos_in_heap[(*it).first]);
            }
        }
        //printf("\n");
        pos_in_heap[heap[sz]]=1;
        swap(heap[1],heap[sz]);
        sz--;
        down_heap(1);
    }
    for(int i=2;i<=n;i++)
    {
        printf("%lld ",res[i]);
    }
}