/*
https://infoarena.ro/problema/dijkstra
*/
#include <fstream>
#include <vector>

using namespace std;

const int INF = 1e9 + 1;

struct arc
{
    int y, c;
};

vector <int> h, d, poz_in_h;

int tata(int p)
{
    return (p - 1) / 2;
}

int fiu_stang(int p)
{
    return (2 * p + 1);
}

int fiu_drept(int p)
{
    return (2 * p + 2);
}

void adauga(int x)
{
    h.push_back(x);
    poz_in_h[x] = (int)h.size() - 1;
    // urca(poz_in_h[x]);
}

void schimb(int p1, int p2)
{
    swap(h[p1], h[p2]);
    poz_in_h[h[p1]] = p1;
    poz_in_h[h[p2]] = p2;
}

void urca(int p)
{
    while (p > 0 && d[h[p]] < d[h[tata(p)]])
    {
        schimb(p, tata(p));
        p = tata(p);
    }
}

void coboara(int p)
{
    int fs = fiu_stang(p), fd = fiu_drept(p), poz_min = p;
    if (fs < (int)h.size() && d[h[fs]] < d[h[poz_min]])
    {
        poz_min = fs;
    }
    if (fd < (int)h.size() && d[h[fd]] < d[h[poz_min]])
    {
        poz_min = fd;
    }
    if (poz_min != p)
    {
        schimb(poz_min, p);
        coboara(poz_min);
    }
}

void sterge()
{
    schimb(0, (int)h.size() - 1);
    h.pop_back();
    coboara(0);
}

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int n, m;
    in >> n >> m;
    h.reserve(n);
    d.resize(n + 1, INF);
    poz_in_h.resize(n + 1);
    vector <arc> e(m);
    vector <vector <int>> lst_s(n + 1);
    for (int i = 0; i < m; i++)
    {
        int x;
        in >> x >> e[i].y >> e[i].c;
        lst_s[x].push_back(i);
    }
    in.close();
    for (int x = 1; x <= n; x++)
    {
        adauga(x);
    }
    d[1] = 0;
    urca(poz_in_h[1]);
    while (!h.empty())
    {
        int x = h.front();
        sterge();
        for (auto i: lst_s[x])
        {
            int y = e[i].y;
            if (d[x] + e[i].c < d[y])
            {
                d[y] = d[x] + e[i].c;
                urca(poz_in_h[y]);
            }
        }
    }
    for (int x = 2; x <= n; x++)
    {
        if (d[x] == INF)
        {
            d[x] = 0;
        }
        out << d[x] << " ";
    }
    out << "\n";
    out.close();
    return 0;
}