#include <cstdio>
 
const int maxn = 50001;
const int inf = 1 << 30;
 
FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w");
 
struct graf
{
    int nod, cost;
    graf *next;
};
 
int n, m;
graf *a[maxn];
int d[maxn], h[maxn], poz[maxn], k;
 
void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}
 
void read()
{
    fscanf(in, "%d %d", &n, &m);
 
    int x, y, z;
    for ( int i = 1; i <= m; ++i )
    {
        fscanf(in, "%d %d %d", &x, &y, &z);
        add(x, y, z);
    }
}
 
void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

/*functia upheap se apeleaza ori de cate ori adaugam in heap un nou nou. In cel mai rau caz
se va apela de N ori - numarul de noduri. Upheap este functia care ridica un nod proaspat introdus
la un nivel la care nu mai incalca proprietatea de heap. Deoarece avem h= log(N) nivele in orice moment
in cel mai rau caz in care introducem de fiecare data un nod ce devine radacina, avem complexitatea O(logN)
Impreuna cu adaugarea de N noduri, obtinem complexitatea N * log(N)*/
void upheap(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;
 
        if ( d[ h[tata] ] > d[ h[what] ] )
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;
 
            swap(tata, what);
 
            what = tata;
        }
        else
            what = 1;
    }
}
 
/*Down heap ese apeleaza ori de cate ori extragem un nod din heap. In cel mai rau caz se va apela de N ori,
daca extragem toate nodurile din heap. Downheap este functia care coboara noul nod radacina pe pozitia, pe
care nu va mai incalca proprietatea de heap. Deoarece avem h = log(N) nivele in orice moment
in cel mai rau caz in de fiecare data cand luam un nou nod radacina acesta ajunge sa devina frunza, avem
complexitatea O(logN). Impreuna cu adaugarea de N noduri, obtinem complexitatea N * log(N)*/
void downheap(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        if ( (what<<1) <= k )
        {
            f = what << 1;
            if ( f + 1 <= k )
                if ( d[ h[f + 1] ] < d[ h[f] ] )
                    ++f;
        }
        else
            return;
 
        if ( d[ h[what] ] > d[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;
 
            swap(what, f);
 
            what = f;
        }
        else
            return;
    }
}

/*Algoritmul lui Dijkstra va analiza de fiecare data muchiile si va alege nodul cu costul 
cel mai bun. In cel mai rau caz va trebui sa analizeze toate muchiile, obtinandu-se asfel O(M)*/
void dijkstra_heap()
{
    for ( int i = 2; i <= n; ++i )
        d[i] = inf, poz[i] = -1;
    poz[1] = 1;
 
    h[++k] = 1;
 
    while ( k )
    {
        int min = h[1];
        swap(1, k);
        poz[ h[1] ] = 1;
        --k;
 
        downheap(1);
 
        graf *q = a[min];
 
        while ( q )
        {
            if ( d[q->nod] > d[min] + q->cost )
            {
                d[q->nod] = d[min] + q->cost;
 
                if ( poz[q->nod] != -1 )
                    upheap( poz[q->nod] );
                else
                {
                    h[++k] = q->nod;
                    poz[ h[k] ] = k;
                    upheap( k );
                }
            }
            q = q->next;
        }
    }
}
 
int main()
{
    read();
    dijkstra_heap();
 
    for ( int i = 2; i <= n; ++i )
        fprintf(out, "%d ", d[i] == inf ? 0 : d[i]);
    fprintf(out, "\n");
 
    return 0;
}