#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <utility>
#include <limits>
#include <queue>

std::ifstream be ("dijkstra.in");
std::ofstream ki ("dijkstra.out");


struct csp
{
    int index, suly;
};

struct lista
{
    csp elem;
    lista* kov;
};

typedef std::vector<lista*> graf_t;
typedef std::list<csp>::iterator iterator_t;
const int INF = std::numeric_limits<int>::max();


void beszur_lista (lista*& x, const csp& uj)
{
    lista* t = new lista;
    t->elem = uj;
    t->kov = x;
    x = t;
}

void torol_lista (lista*& x)
{
    while (x != NULL)
    {
        lista* t = x->kov;
        delete x;
        x = t;
    }
}

std::vector<csp> kupac;
std::vector<int> poz;

void beszur(int elem, int sorszam)
{
    int akt_pos;
    if (poz[sorszam] == INF)
    {
        kupac.push_back({sorszam, elem});
        poz[sorszam] = kupac.size()-1;
        akt_pos = kupac.size()-1;
    }
    else
    {
        kupac[poz[sorszam]].suly = elem;
        akt_pos = poz[sorszam];
    }
    while (akt_pos>1 && kupac[akt_pos].suly < kupac[akt_pos/2].suly)
    {
        std::swap (kupac[akt_pos], kupac[akt_pos/2]);
        poz[kupac[akt_pos].index] = akt_pos;
        poz[kupac[akt_pos/2].index] = akt_pos/2;
        akt_pos /= 2;
    }
}

void kivesz()
{
    kupac[1] = kupac.back();
    kupac.pop_back();
    poz[kupac[1].index] = 1;
    int akt_pos(1), p;
    do
    {
        p = akt_pos;
        if (p*2 < kupac.size() && kupac[p*2].suly < kupac[akt_pos].suly) akt_pos = p*2;
        if (p*2+1 < kupac.size() && kupac[p*2+1].suly < kupac[akt_pos].suly) akt_pos = p*2+1;
        std::swap (kupac[p], kupac[akt_pos]);
        poz[kupac[p].index] = p;
        poz[kupac[akt_pos].index] = akt_pos;
    } while (p != akt_pos);
}

csp min()
{
    return kupac[1];
}

bool ures()
{
    return kupac.size() == 1;
}

void dijkstra (graf_t& graf, int start, std::vector<int>& hossz)
{
    hossz.resize (graf.size(), INF);
    kupac.resize (1);
    poz.resize (graf.size(), INF);
    hossz[start] = 0;
    beszur (0, start);


    while (!ures())
    {
        int u = min().index;
        kivesz();
        lista* akt = graf[u];
        while (akt != NULL)
        {
            int v = akt->elem.index;
            int suly = akt->elem.suly;
            if (hossz[u]+suly < hossz[v])
            {
                hossz[v] = hossz[u]+suly;
                beszur(hossz[v], v);
            }
            akt = akt->kov;
        }
    }
}

int main()
{
    int n, m, i, csp1, csp2, suly;
    graf_t g;

    be >> n >> m;
    g.resize (n+1, NULL);
    for (i=0; i<m; i++)
    {
        be >> csp1 >> csp2 >> suly;
        beszur_lista (g[csp1], {csp2, suly});
    }
/*
    for (i=1; i<=n; i++)
    {
        lista* t = g[i];
        while (t != NULL)
        {
            std::cout << i << " -> " << t->elem.index << "\n";
            t = t->kov;
        }
    }
*/
    std::vector<int> hossz;
    dijkstra (g, 1, hossz);
    for (i=1; i<=n; i++) torol_lista (g[i]);

    for (unsigned i=2; i<hossz.size(); i++)
    {
        if (hossz[i] == INF) ki << "0 ";
        else ki << hossz[i] << " ";
    }
}