#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,i,q,x,y,z,aux,a[50001],dist[50001],drum[50001],poz[50001];
struct nod
{
    int y,cost;
}nd;
vector <nod> v[50001];
vector <nod>::iterator it;
void pushup(int x)
{
    int val;
    val=dist[a[x]];
    while(x>1 && val<dist[a[x/2]])
    {
        swap(a[x],a[x/2]);
        poz[a[x]]=x;
        poz[a[x/2]]=x/2;
        x/=2;
    }
}
void pushdown(int x)
{
    int son;
    do
    {
        son=0;
        if(x*2<=q)
        {
            son=x*2;
            if(son+1<=q && dist[a[son+1]]<dist[a[son]])
                son++;
            if(dist[a[son]]>=dist[a[x]])
                son=0;
        }
        if(son)
        {
            swap(a[x],a[son]);
            swap(poz[a[x]],poz[a[son]]);
            x=son;
        }
    }
    while(son);
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d\n",&x,&y,&z);
        nd.y=y;
        nd.cost=z;
        v[x].push_back(nd);
    }
    for(i=2;i<=n;i++)
    {
        dist[i]=1000000001;
        drum[i]=1000000001;
        a[++q]=i;/// heap-ul
        poz[i]=q;/// pozitia elementului i in heap
    }
    x=1;
    aux=q;
    while(1)
    {
        for(it=v[x].begin();it!=v[x].end();it++)
        {
            nd=*it;/// pentru fiecare vecin nevizitat
            if(drum[x]+nd.cost<drum[nd.y])/// verific daca am un drum mai bun
            {
                drum[nd.y]=drum[x]+nd.cost;
                dist[nd.y]=drum[nd.y];
                pushup(poz[nd.y]);/// dupa ce actualizez lungimea,refac heap-ul
            }
        }
        if(!aux)
            break;
        x=a[1];
        dist[x]=1000000001;/// dupa ce este folosit,fiecarui element i se asociaza o valoare mare
        aux--;
        pushdown(1);/// refac heap-ul dupa folosirea fiecarui element
    }
    for(i=2;i<=n;i++)
        if(drum[i]>=1000000001)
            printf("0 ");
        else
            printf("%d ",drum[i]);
    printf("\n");
    return 0;
}