/*#include <bits/stdc++.h>
#define infinit 2000000000
using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");
// 10   1 3 0 5 2 4 7 9 8 6

struct graf{
    int nod;
    int cost;
};

int n, p;
bool checked[50005];
vector <graf> graphs[50005];
graf heap[251000], dist[50005];

void up_heap(int k)
{
    int gud;
    while(k > 1)
    {
        gud = k>>1;
        if(heap[gud].cost > heap[k].cost)
            swap(heap[gud], heap[k]), k = gud;
        else
            break;
    }
}

void blend_in_heap(int k, int heap_len)
{
    int len;
    while(k <= (heap_len>>1))
    {
        len = k<<1;
        if(heap[len + 1].cost < heap[len].cost)
        len++;
        if (heap[len].cost < heap[k].cost)
            swap(heap[len], heap[k]), k = len;
        else break;
    }
}

void heap_infinity(int k)
{
    int i;
    for(i = 1; i <= k; i++)
        heap[i].cost = infinit;
}
void construct_distance()
{
    int i;
    for(i = 1; i <= n; i++)
        dist[i].cost = infinit, dist[i].nod = i;
}

void dijkstra(int nod_start)
{
    int heap_len = 0, k, var;
    unsigned i, len;
    dist[nod_start].cost = 0;
    checked[nod_start] = 1;
    len = graphs[nod_start].size();
    for(i = 0; i < len; i++)
    {
        var = graphs[nod_start][i].nod;
        if(graphs[nod_start][i].cost < dist[var].cost)
        {
        heap_len++;
        dist[graphs[nod_start][i].nod].cost = graphs[nod_start][i].cost;
        heap[heap_len] = dist[graphs[nod_start][i].nod];
        up_heap(heap_len);
        }
    }
    while(heap_len > 0)
    {
        k = heap[1].nod;
        if(!checked[k])
        {
            checked[k] = 1;
            len = graphs[k].size();
            for(i = 0; i < len; i++)
            {
                var = graphs[k][i].nod;
                if(!checked[var])
                {
                    if(dist[k].cost + graphs[k][i].cost < dist[var].cost)
                    {
                        dist[var].cost = dist[k].cost + graphs[k][i].cost, heap_len++;
                        heap[heap_len] = dist[graphs[k][i].nod];
                        up_heap(heap_len);
                    }
                }
            }
            heap[1] = heap[heap_len];
            heap_len--;
            blend_in_heap(1, heap_len);
        }
        else
        {
           heap[1] = heap[heap_len];
           heap_len--;
           blend_in_heap(1, heap_len);
        }
    }
}

int main()
{
    int x, ct = 0;
    graf var;
    fin >> n >> p;
    while(fin >> x >> var.nod >> var.cost)
        graphs[x].push_back(var), ct++;
    heap_infinity(ct + 40);
    construct_distance();
    dijkstra(1);
    for(int i = 2; i <= n; i++)
    {
        if(dist[i].cost == infinit)
        fout << 0 << " ";
        else
        fout << dist[i].cost << " ";
    }

    return 0;
}
for(i = 1; i <= n; i++)
    {
        fout << i << " : ";
        for(j = 0; j < graphs[i].size(); j++)
            fout << graphs[i][j].nod << " si " << graphs[i][j].cost << " ";
        fout << endl;
    }
    */
#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;

}



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;

    }

}



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;

    }

}



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;

}