#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <set>
#include <climits> 

using namespace std;

struct Item {
    int id;
    int totalDistance;
    int distance;

    Item(int id, int totalDistance, int distance)
        : id(id), totalDistance(totalDistance), distance(distance) {}
    

    bool operator<(const Item& other) const {
        return totalDistance > other.totalDistance; /
    }
};

// Dijkstra's algorithm function
vector<int> dijkstrasAlgorithm(int start, const vector<vector<pair<int, int>>>& edges) {
    vector<int> result(edges.size(), INT_MAX); 
    result[start] = 0; 

    priority_queue<Item> q;
    set<int> visited;


    for (const auto& edge : edges[start]) {
        q.push(Item(edge.first, edge.second, edge.second));
    }

    visited.insert(start);

    while (visited.size() < edges.size() && !q.empty()) {
        Item nextNode = q.top();
        q.pop();

        if (visited.count(nextNode.id)) {
            continue;
        }

        visited.insert(nextNode.id);
        result[nextNode.id] = nextNode.totalDistance;


        for (const auto& edge : edges[nextNode.id]) {
            if (!visited.count(edge.first)) {
                q.push(Item(edge.first, edge.second + nextNode.totalDistance, edge.second));
            }
        }
    }

    return result;
}

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

    int N, M;
    fin >> N >> M;

  
    vector<vector<pair<int, int>>> edges(N + 1);

  
    for (int i = 0; i < M; i++) {
        int A, B, C;
        fin >> A >> B >> C;
        edges[A].push_back({B, C});
    }


    vector<int> result = dijkstrasAlgorithm(1, edges);


    for (int i = 2; i <= N; i++) {
        if (result[i] == INT_MAX) {
            fout << -1 << " "; 
        } else {
            fout << result[i] << " ";
        }
    }
    fout << endl;

    return 0;
}