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

using namespace std;

const int INF = 1e9 + 1;

struct arc
{
    int y, c;
};

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int n, m;
    in >> n >> m;
    vector <int> d(n + 1, INF);
    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();
    priority_queue <pair <int, int>, vector <pair <int, int>>,
                   greater <pair <int, int>>> h;
    d[1] = 0;
    h.push({0, 1});
    vector <bool> prel(n + 1, false);
    while (!h.empty())
    {
        int x = h.top().second;
        h.pop();
        if (!prel[x])
        {
            prel[x] = true;
            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;
                    h.push({d[y], y});
                }
            }
        }
    }
    for (int x = 2; x <= n; x++)
    {
        if (d[x] == INF)
        {
            d[x] = 0;
        }
        out << d[x] << " ";
    }
    out << "\n";
    out.close();
    return 0;
}