#include <cstdio>
#include <cstring>
#include <fstream>
#define Nmx 50001
#define INF 0x3f3f3f3f

using namespace std;

int n,m,Heap[4*Nmx],nr,poz[4*Nmx],cost[Nmx];

struct nod
{
    int inf,c;
    nod *urm;
};
nod *G[Nmx];

ifstream fin("dijkstra.in");

void add(int x,int y,int c)
{
    nod *aux=new nod;
    aux->inf = y;
    aux->c = c ;
    aux->urm = G[x];
    G[x] = aux;
}

void read()
{
    int x,y,c;
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        add(x,y,c);
    }
}

void up(int k)
{
    while(k>1&&cost[Heap[k/2]]>cost[Heap[k]])
    {
        int aux=Heap[k/2];
        Heap[k/2]=Heap[k];
        Heap[k]=aux;
        poz[Heap[k]]=k/2;
        poz[Heap[k/2]]=k;
        k/=2;
    }
}

void down(int k)
{
    while(k*2<=nr)
    {
        int p=k*2;
        if(p+1<=nr&&cost[Heap[p+1]]<cost[Heap[p]])
            p=p+1;
        int aux=Heap[p];
        Heap[p]=Heap[k];
        poz[Heap[p]]=k;
        poz[Heap[k]]=p;
        k=p;
    }
}

void solve()
{
    for(int i=1;i<=n;++i)
    {
        cost[i]=INF;
        poz[i]=-1;
    }
    cost[1]=0;
    poz[1]=1;
    Heap[++nr]=1;
    while(nr)
    {
        int x = Heap[1];
        poz[Heap[nr]]=1;
        poz[Heap[1]]=-1;
        Heap[1]=Heap[nr--];
        down(1);
        for(nod *p=G[x];p;p=p->urm)
            if(cost[p->inf]>cost[x]+p->c)
            {
                cost[p->inf]=cost[x]+p->c;
                if(poz[p->inf]==-1)
                {
                    Heap[++nr]=p->inf;
                    poz[p->inf]=nr;
                    up(nr);
                }
                else up(poz[p->inf]);
            }
    }
    for(int i=2;i<=n;++i)
        if(cost[i]==INF)
            printf("0 ");
        else printf("%d ",cost[i]);
    printf("\n");
}

int main()
{
    freopen("dijkstra.out","w",stdout);
    read();
    solve();
    return 0;
}