#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;
};
typedef std::vector<std::list<csp> > graf_t;
typedef std::pair<int, int> par;
typedef std::list<csp>::iterator iterator_t;
const int INF = std::numeric_limits<int>::max();


class kupac
{
    std::vector<csp> x;
    std::vector<int> poz;

public:
    kupac(int n)
    {
        x.resize (1);
        poz.resize(n+1, INF);
    }
    void beszur(int elem, int sorszam)
    {
        int akt_pos;
        if (poz[sorszam] == INF)
        {
            x.push_back({sorszam, elem});
            poz[sorszam] = x.size()-1;
            akt_pos = x.size()-1;
        }
        else
        {
            x[poz[sorszam]].suly = elem;
            akt_pos = poz[sorszam];
        }
        while (akt_pos>1 && x[akt_pos].suly < x[akt_pos/2].suly)
        {
            std::swap (x[akt_pos], x[akt_pos/2]);
            poz[x[akt_pos].index] = akt_pos;
            poz[x[akt_pos/2].index] = akt_pos/2;
            akt_pos /= 2;
        }
    }
    void kivesz()
    {
        x[1] = x.back();
        x.pop_back();
        poz[x[1].index] = 1;
        int akt_pos(1), p;
        do
        {
            p = akt_pos;
            if (p*2 < x.size() && x[p*2].suly < x[akt_pos].suly) akt_pos = p*2;
            if (p*2+1 < x.size() && x[p*2+1].suly < x[akt_pos].suly) akt_pos = p*2+1;
            std::swap (x[p], x[akt_pos]);
            poz[x[p].index] = p;
            poz[x[akt_pos].index] = akt_pos;
        } while (p != akt_pos);
    }
    csp min()
    {
        return x[1];
    }
    bool ures()
    {
        return x.size() == 1;
    }
};

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


    while (!q.ures())
    {
        int u = q.min().index;
        q.kivesz();
        for (iterator_t i=graf[u].begin(); i != graf[u].end(); i++)
        {
            int v = i->index;
            int suly = i->suly;
            if (hossz[u]+suly < hossz[v])
            {
                hossz[v] = hossz[u]+suly;
                q.beszur(hossz[v], v);
            }
        }
    }
}

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

    be >> n >> m;
    g.resize (n+1);
    for (i=0; i<m; i++)
    {
        be >> csp1 >> csp2 >> suly;
        g[csp1].push_back ({csp2, suly});
    }

    std::vector<int> hossz;
    dijkstra (g, 1, hossz);

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