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

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

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

    // Lista de adiacenta: adj[nod] = vector de (vecin, cost)
    vector<vector<pair<int, int>>> adj(n + 1);

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        f >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    // dist[i] = distanta minima de la nodul 1 la nodul i
    vector<long long> dist(n + 1, LLONG_MAX);
    dist[1] = 0;

    // Min-heap: (distanta, nod)
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, 1});

    while (!pq.empty())
    {
        long long d = pq.top().first;
        int nod = pq.top().second;
        pq.pop();

        // Daca am gasit deja un drum mai scurt, ignoram
        if (d > dist[nod])
            continue;

        // Relaxam vecinii
        for (auto &muchie : adj[nod])
        {
            int vecin = muchie.first;
            int cost = muchie.second;

            if (dist[nod] + cost < dist[vecin])
            {
                dist[vecin] = dist[nod] + cost;
                pq.push({dist[vecin], vecin});
            }
        }
    }

    // Afisam distantele de la nodul 1 la nodurile 2, 3, ..., N
    for (int i = 2; i <= n; i++)
    {
        if (dist[i] == LLONG_MAX)
            g << 0; // Nu exista drum
        else
            g << dist[i];

        if (i < n)
            g << " ";
    }
    g << "\n";

    return 0;
}