//
// Created by tudor on 1/2/2021.
//
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <fstream>
#include <limits>

#define intMax std::numeric_limits<int>::max()

using namespace std;

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

typedef pair<int, int> iPair;

struct GraphNode {
    bool wasProcessed = false;
    int distanceFromSource = intMax;
    vector <iPair> Edges;

    void addEdge(int dr, int cost) {
        Edges.emplace_back(dr, cost);
    }
};

struct Graph {
    int nodeCnt, edgeCnt;
    GraphNode *nodes;
    priority_queue<iPair,vector<iPair>,greater<>> targetNodes;

    Graph(int V, int E)
    {
        this->nodeCnt = V;
        this->edgeCnt = E;
        nodes = new GraphNode[V];

        for(int i = 0, a, b, c; i < edgeCnt; i++)
        {
            fin >> a >> b >> c;
            addEdge(a - 1, b - 1, c);
        }
    }

    ~Graph() {
        delete[] nodes;
    }

    void addEdge(int st, int dr, int cost) const {
        nodes[st].addEdge(dr, cost);
    }

    void dijkstraNodeProcess(GraphNode* node) {
        if(node->wasProcessed) {
            return;
        }

        node->wasProcessed = true;

        for(auto & edge : node->Edges) {
            auto neighbour = &nodes[edge.first];
            if(neighbour->wasProcessed) {
                continue;
            }
            if(neighbour->distanceFromSource > node->distanceFromSource + edge.second) {
                neighbour->distanceFromSource = node->distanceFromSource + edge.second;
                targetNodes.push({neighbour->distanceFromSource, edge.first});
            }
        }
    }

    void dijkstra() {
        auto source = &nodes[0];
        source->distanceFromSource = 0;
        targetNodes.push({0,0});
        while(!targetNodes.empty())
        {
            int x = targetNodes.top().second;
            targetNodes.pop();
            dijkstraNodeProcess(&nodes[x]);
        }
    }

    void displayDijkstra() const {
        for (int i = 1;i < nodeCnt; i++)
            if(nodes[i].distanceFromSource == intMax)
                fout << 0 << ' ';
            else
                fout << nodes[i].distanceFromSource << ' ';
    }
};

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

    Graph graph(n, m);

    graph.dijkstra();
    graph.displayDijkstra();
}