#include <stdio.h>

#define Nmax 50100

struct Nod { int a,c; Nod *x;};

Nod *l[Nmax];
int n,m,sursa;
char v[Nmax];
int dist[Nmax];

int h[Nmax], nr, p[Nmax];

void up(int nod)
{
    if (nod <= 1) return;
    if (dist[h[nod]] < dist[h[nod/2]])
    {
        int tmp = h[nod/2];
        h[nod/2] = h[nod];
        h[nod] = tmp;
        p[h[nod]] = nod;
        p[h[nod/2]] = nod/2;
        up(nod/2);
    }
}

void insert(int nod)
{
    h[++nr] = nod;
    p[nod] = nr;
    up(nr);
}

void down(int nod)
{
    int min = nod;
    if (2*nod <= nr) if (dist[h[2*nod]] < dist[h[min]]) min = 2*nod;    
    if (2*nod+1 <= nr) if (dist[h[2*nod+1]] < dist[h[min]]) min = 2*nod+1;    
    if (min != nod)
    {
        int tmp = h[nod];
        h[nod] = h[min];
        h[min] = tmp;
        p[h[min]] = min;
        p[h[nod]] = nod;
        down(min);        
    }    
}

void fix(int nod)
{
    up(p[nod]);
}

int pop()
{
    int ret = h[1];
    h[1] = h[nr--];
    down(1);
    return ret;    
}

void citire()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d%d", &n,&m);
    
    sursa = 1;
    
    for (int i=1;i<=m;++i)
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        Nod *q = new Nod;
        q->a = b;
        q->c = c;
        q->x = l[a];
        l[a] = q;    
    }    
}

#define Inf 1234567891

void afis()
{
    for (int i=2;i<=n;++i) if(dist[i] != Inf)
    printf("%d ", dist[i]); else printf("0 ");   
    printf("\n");
}

void relaxeaza(int nod)
{
    v[nod] = 1;    
    for (Nod *it=l[nod];it;it=it->x)
    if (dist[nod]+it->c < dist[it->a])
    {
        dist[it->a] = dist[nod] + it->c;
        fix(it->a);
    }
}

void dijkstra()
{
    for (int i=0;i<=n;++i)
    dist[i] = Inf;
    dist[sursa] = 0;
    
    for (int i=1;i<=n;++i)
    insert(i);    
    
    for (int pas=1;pas<=n;++pas)
    {
        int min = pop();
        relaxeaza(min);    
    }
}
int main()
{    
    citire();
    
    dijkstra();
    
    afis();
    
    return 0;
}