#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>

const int NMAX = 50001;
const int INF = std::numeric_limits<int>::max();

std::vector<std::pair<int, int>> G[NMAX];
std::vector<int> dist;
std::set<std::pair<int, int>> heap;
int N, M;

int main()
{
    std::ifstream f("dijkstra.in");

    int x, y, c;

    f >> N >> M;
    while (M--)
    {
        f >> x >> y >> c;
        G[x].push_back(std::make_pair(y, c));
    }

    f.close();

    dist.resize(N + 1);
    std::fill(dist.begin(), dist.end(), INF);
    dist[1] = 0;

    heap.insert(std::make_pair(0, 1));

    while (!heap.empty())
    {
        int node = heap.begin()->second;
        heap.erase(heap.begin());

        for (auto it = G[node].begin(); it != G[node].end(); ++it)
        {
            int to = it->first;
            int cost = it->second;
            if (dist[to] > dist[node] + cost)
            {
                if (dist[to] != INF)
                {
                    heap.erase(std::make_pair(dist[to], to));
                }

                dist[to] = dist[node] + cost;
                heap.insert(std::make_pair(dist[to], to));
            }
        }
    }

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

    return 0;
}