#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[250010], 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;

    graf var;

    fin >> n >> p;

    while(fin >> x >> var.nod >> var.cost)

        graphs[x].push_back(var);

    heap_infinity(p + 3);

    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;

}