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

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

class Graph
{
private:
    int n;
    vector<vector<pair<int, int>>> adj;
    vector<int> dist;
public:
    Graph(int n) : n(n), adj(n + 1)
    {
        dist.resize(n + 1, 0);
    }

    void AddEdge(int a, int b, int c)
    {
        adj[a].emplace_back(b, c);
    }

    void Dijkstra(int src)
    {

        vector<bool> vis(n + 1, false);
        priority_queue<pair<int, int>> pq;

        pq.emplace(0, src);

        while (!pq.empty())
        {

            int d, node;
            d = - pq.top().first;
            node = pq.top().second;
            pq.pop();

            if (vis[node] == false)
            {
                vis[node] = true;
                dist[node] = d;
                for (auto itr : adj[node])
                {

                    int nbh, cost;
                    nbh = itr.first;
                    cost = itr.second;
                    pq.emplace(-(d + cost), nbh);
                }

            }
        }
    }
    void PrintDist()
    {
        for (int i = 2; i <= n; ++i)
            out << dist[i] << " ";
    }
};
int main()
{
    int n, m;
    in >> n >> m;

    Graph graph(n);
    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        in >> a >> b >> c;
        graph.AddEdge(a, b, c);
    }

    graph.Dijkstra(1);
    graph.PrintDist();
    return 0;
}