#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct cmp
{
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) const
    {
        return a.first > b.first;
    }
};

const int N = 5e5, INF = 5e6;
vector<pair<int, int>> lista_ad[N + 1];
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
int d[N + 1];

int main()
{
    int n, m;
    in >> n >> m;

    int u, v, c;
    for (int i = 0; i < m; i++)
    {
        in >> u >> v >> c;
        lista_ad[u].push_back({v, c});
    }

    pq.push({0, 1});
    d[1] = 0;

    for (int i = 2; i <= n; i++)
        d[i] = INF;

    while (!pq.empty())
    {
        pair<int, int> curent = pq.top();
        int dist_curent = curent.first;
        int idx_curent = curent.second;
        pq.pop();

        if (d[idx_curent] == dist_curent)
            for (pair<int, int> x : lista_ad[idx_curent])
            {
                int v = x.first;
                int cost_m = x.second;

                if (d[v] > d[idx_curent] + cost_m)
                {
                    d[v] = d[idx_curent] + cost_m;
                    pq.push({d[v], v});
                }
            }
    }

    for (int i = 2; i <= n; i++)
    {
        if (d[i] == INF)
            d[i] = 0;
        out << d[i] << " ";
    }
    return 0;
}