// https://www.infoarena.ro/problema/dijkstra - Szücs Patrik - Kevin
#include <fstream>
#include <queue>
#include <vector>
#include <climits>

#define pr std::pair<int, int>

int main()
{
    int n, m;

    std::ifstream in("dijkstra.in");
    in >> n >> m;

    std::vector<std::vector<pr>> graf(n + 1);
    while (m--)
    {
        int x, y, w;
        in >> x >> y >> w;

        graf[x].push_back({y, w});
    }
    in.close();

    //-------------------------------------------------------

    std::vector<int> dist(n + 1, INT_MAX);
    dist[1] = 0;

    std::priority_queue<pr, std::vector<pr>, std::greater<pr>> q;
    q.push({0, 1});

    while (!q.empty())
    {
        int w = q.top().first, from = q.top().second; // suly
        q.pop();

        if (dist[from] == w)
        {
            for (auto e : graf[from])
            {
                int to = e.first, weight = e.second;

                if (dist[to] > dist[from] + weight)
                {
                    dist[to] = dist[from] + weight;
                    q.push({dist[to], to});
                }
            }
        }
    }

    //-------------------------------------------------------

    std::ofstream out("dijkstra.out");
    for (int i = 2; i <= n; i++)
    {
        out << ((dist[i] == INT_MAX) ? 0 : dist[i]) << ' ';
    }

    out.close();
    return 0;
}