#include <stdio.h>
#define NM 50001

int n, m, hsize;
int i, j, k, g;
int h[NM], pos[NM];
int d[NM];
int u, s[NM];
typedef struct nod {
    int vf, dist;
    nod* urm;
} NOD, *PNOD;
PNOD l[NM];

void Add(int i, int j, int dist);
void BuildHeap();
void RebuildHeap(int poz);
void MoveUp(int nod);   
int ExtractMin();
void Dijkstra();

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for ( g = 1; g <= m; g++ )
        scanf("%d %d %d", &i, &j, &k),
        Add(i, j, k);
       
    Dijkstra();
    
    for ( i = 2; i <= n; i++ )
        printf("%d ", (d[i] == 1000000 ? 0 : d[i]));
    printf("\n");
    
    return 0;
}

void Add(int i, int j, int k)
{
    PNOD q = new NOD;
    q->vf = j;
    q->dist = k;
    q->urm = l[i];
    l[i] = q;
}

void BuildHeap()
{
    for ( i = 1; i <= n; i++ )
        d[i] = 1000000, h[i] = pos[i] = i;
    d[1] = 0;
    hsize = n;
    for ( i = n/2; i >= 1; i-- )
        RebuildHeap(i);
}

void RebuildHeap(int poz)
{
    int value = h[poz]; 
    int parent = poz; 
    int son = 2*parent;
    
    while ( son <= hsize )
    {
        if ( son < hsize && d[h[son]] > d[h[son+1]] ) son++;
        if ( d[h[son]] < d[value] )
        {
            h[parent] = h[son];
            pos[h[parent]] = parent;
            parent = son;
            son = 2*parent;
        }
        else break;
    }
    h[parent] = value;
    pos[value] = parent;
}

void MoveUp(int nod)
{
    int value = nod;
    int son = pos[nod];
    int parent = son/2;
    
    while ( parent && d[value] < d[h[parent]] )
    {
        h[son] = h[parent];
        pos[h[son]] = son;
        son = parent;
        parent = son/2;
    }
    h[son] = value;
    pos[value] = son;
}

int ExtractMin()
{
    int dmin = h[1];
    h[1] = h[hsize];
    h[hsize] = 0;
    hsize--;
    RebuildHeap(1);
    return dmin;
}

void Dijkstra()
{
    BuildHeap();
    while ( hsize )
    {
        u = ExtractMin();
        s[u] = 1;
        for ( PNOD q = l[u]; q; q = q->urm )
            if ( !s[q->vf] && d[q->vf] > d[u] + q->dist )
            {
                d[q->vf] = d[u] + q->dist;
                MoveUp(q->vf);
            }
    }
}