# include <cstdio>
# include <vector>

using namespace std;

const int N = 50000;

struct Muchie
{
    int nod, cost;
};

Muchie getMuchie (int nod, int cost)
{
    Muchie m;

    m. nod = nod;
    m. cost = cost;

    return m;
}

vector <Muchie> v [N + 1];
int rez [N + 1], heap [N + 1];
bool viz [N + 1];
int n, m, lHeap;

void citeste ()
{
    int i, n1, n2, c;

    scanf ("%d %d", & n, & m);

    for (i = 1; i <= n; i ++)
    {
        scanf ("%d %d %d", & n1, & n2, & c);
        v [n1]. push_back (getMuchie (n2, c));
    }
}

void init ()
{
    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);

    citeste ();
}

void change (int poz1, int poz2)
{
    int aux = heap [poz1];

    heap [poz1] = heap [poz2];
    heap [poz2] = aux;
}

void insertHeap (int nod)
{
    int poz;

    heap [++ lHeap] = nod;
    poz = lHeap / 2;

    while (rez [heap [poz]] > rez [nod])
    {
        change (poz * 2, poz);
        poz /= 2;
    }
}

void stergeHeap (int p)
{
    int poz = p, aux, aux1, aux2;
    bool f = false;

    heap [p] = heap [lHeap --];

    while (! f)
    {
        aux = rez [heap [poz]];
        aux1 = rez [heap [poz * 2]];
        aux2 = rez [heap [poz * 2 + 1]];

        if (aux1 < aux2 && aux1 != 0)
            if (aux1 < aux)
            {
                change (poz, poz * 2);
                poz *= 2;
            }
            else
                f = true;
        else
            if (aux2 < aux && aux2 != 0)
            {
                change (poz, poz * 2 + 1);
                poz = poz * 2 + 1;
            }
            else
                f = true;
    }
}

void dijkstra (int nod)
{
    int i, nodC;
    Muchie muchieC;

    insertHeap (nod);

    while (lHeap)
    {
        nodC = heap [1];
        viz [nodC] = true;

        for (i = 0; i < v [nodC]. size (); i ++)
        {
            muchieC = v [nodC] [i];

            if (viz [muchieC. nod] == false)
                if (rez [muchieC. nod] == 0 || rez [nodC] + muchieC. cost < rez [muchieC. nod])
                {
                    rez [muchieC. nod] = rez [nodC] + muchieC. cost;
                    insertHeap (muchieC. nod);
                }
        }

        stergeHeap (1);
    }
}

void afisare ()
{
    int i;

    for (i = 2; i <= n; i ++)
        printf ("%d ", rez [i]);
}

int main ()
{
    init ();
    dijkstra (1);
    afisare ();

    return 0;
}