#include <bits/stdc++.h>

using namespace std;
int Heap[50001],cst[50001],len,x,y,z,i,n,m,mn,pos[50001],a;
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 nxtson(int nod)
{
    if(cst[Heap[leftson(nod)]]<cst[Heap[nod]])
        if(cst[Heap[rightson(nod)]]>=cst[Heap[leftson(nod)]]) return leftson(nod);
    if(cst[Heap[rightson(nod)]]<cst[Heap[nod]])
        if(cst[Heap[rightson(nod)]]<=cst[Heap[leftson(nod)]]) return rightson(nod);
     return 0;

}
int down(int nod)
{
    int son=nxtson(nod);
    while(Heap[son])
    {

        swap(pos[Heap[nod]],pos[Heap[son]]);
        swap(Heap[son],Heap[nod]);
        nod=son;
        son=nxtson(nod);
    }

}
int up(int nod)
{
    int dad=father(nod);
    while(cst[Heap[nod]]<cst[Heap[dad]]&&dad)
    {
        swap(pos[Heap[nod]],pos[Heap[dad]]);
        swap(Heap[nod],Heap[dad]);
        nod=dad;
        dad=father(nod);
    }
}
void del (int nod)
{
    pos[Heap[nod]]=len;
    pos[Heap[len]]=1;
    Heap[nod]=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++)
        if(cst[i]==999999) printf("0 ");
    else
        printf("%d ",cst[i]);




    return 0;
}