#include <bits/stdc++.h>

using namespace std;
int Heap[50001],cst[50001],len,x,y,z,i,n,m,mn,pos[50001];
vector < int > v[50001];
vector < int > val[50001];
inline int father(int nod)
{
    return nod/2;
}
inline int leftson(int nod)
{
    return 2*nod;
}
inline int rightson(int nod)
{
    return 2*nod+1;
}
int son (int nod)
{
    if(cst[Heap[leftson(nod)]]<cst[Heap[nod]])
        if(cst[Heap[leftson(nod)]]<=cst[Heap[rightson(nod)]])
        return leftson(nod);
    if(cst[Heap[rightson(nod)]]<cst[Heap[nod]])
        if(cst[Heap[leftson(nod)]]>=cst[Heap[rightson(nod)]])
        return rightson(nod);
    return 0;
}
int down (int nod)
{
    while(son(nod))
    {
        swap(Heap[nod],Heap[son(nod)]);
         swap(pos[Heap[nod]],pos[Heap[son(nod)]]);
        nod=son(nod);
    }
}
int up (int nod)
{
    while(cst[Heap[father(nod)]]>cst[Heap[nod]])
    {
      swap(Heap[father(nod)],Heap[nod]);
        swap(pos[Heap[nod]],pos[Heap[father(nod)]]);
      nod=father(nod);
    }
}
int del (int nod)
{
    Heap[nod]=Heap[len];
    swap(pos[Heap[nod]],pos[Heap[len]]);
    len--;
    down(nod);
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back(y);
        val[x].push_back(z);

    }
    for(i=1;i<=n;i++) Heap[i]=i,pos[i]=i;
    cst[1]=0;
    for(i=2;i<=n;i++)
        cst[i]=999999;
    len=n;
    while(len)
    {
        mn=Heap[1];
        del(1);

        for(i=0;i<v[mn].size();i++)
        if(cst[mn]+val[mn][i]<cst[v[mn][i]])
            {
                cst[v[mn][i]]=cst[mn]+val[mn][i];
                up(pos[v[mn][i]]);
            }

    }
    for(i=2;i<=n;i++)
        printf("%d ",cst[i]);



    return 0;
}