#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <fstream>
#include <limits>

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

using namespace std;

typedef pair<int, int> iPair;

const int N_MAX = 100005;

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

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

struct CompareNodes
{
    bool operator() (const GraphNode* st,
                     const GraphNode* dr)
    {
        return st->distanceFromSource < dr->distanceFromSource;
    }
};

typedef priority_queue<GraphNode*, vector<GraphNode*>, CompareNodes> pq_graph;

struct Graph {
    GraphNode nodes[N_MAX];
    pq_graph targetNodes;

    void addEdge(int st, int dr, int cost) {
        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->distanceFromSource > node->distanceFromSource + edge.second) {
                neighbour->distanceFromSource = node->distanceFromSource + edge.second;
                targetNodes.push(neighbour);
            }
        }
    }

    void dijkstra() {
        auto source = &nodes[1];
        source->distanceFromSource = 0;
        dijkstraNodeProcess(source);

        while(!targetNodes.empty()) {
            auto nodeToProcess = targetNodes.top();
            targetNodes.pop();
            dijkstraNodeProcess(nodeToProcess);
        }
    }
} graph;





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

    int n, m;
    fin >> n >> m;
    for(int i = 0, st, dr, c; i < m; i++) {
        fin >> st >> dr >> c;
        graph.addEdge(st, dr, c);
    }

    graph.dijkstra();

    for(int i = 2; i <= n; i++) {
        if(graph.nodes[i].distanceFromSource == intMax) {
            fout << 0 << ' ';
        }
        else {
            fout << graph.nodes[i].distanceFromSource << ' ';
        }
    }

    return 0;
}