#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#include <array>
#include <stack>
#include <algorithm>

#define maxSize 100001
#define maxInt (1<<30)-1

using namespace std;

vector<vector<pair<int, int>>> readAdjacencyListWeighted(ifstream& fin, int nodes, int edges, bool isDirected = false) {
    vector<vector<pair<int, int>>> adjList(nodes + 1);
    for (int i = 0; i < edges; i++) {
        int x, y, weight;
        fin >> x >> y >> weight;
        adjList[x].emplace_back(y, weight);
        if (!isDirected) {
            adjList[y].emplace_back(x, weight);
        }
    }
    return adjList;
}

vector<int> dijkstra(const vector<vector<pair<int, int>>>& adjList, const int& start) {
    bitset<maxSize> visited;
    priority_queue<pair<int, int>> heap;
    vector<int> distance;
    
    distance.resize(adjList.size(), maxInt);
    distance[start] = 0;
    heap.push(make_pair(0, start));
    
    while(!heap.empty()) {
        // Get the node with the smallest distance
        const int u = heap.top().second;
        heap.pop();

        if (!visited[u]) {
            visited[u] = true;
             // Traverse all neighbors
            for (const auto [v, weight] : adjList[u]) {
                if (distance[v] > distance[u] + weight) {
                     // Relax the edge
                    distance[v] = distance[u] + weight;
                    heap.push(make_pair(-distance[v], v));
                }
            }
        }
    }

    // Replace maxInt with -1 for unreachable nodes
    for (int i = 1; i <= adjList.size(); i++) {
        if (distance[i] == maxInt) {
            distance[i] = -1;
        }
    }

    return distance;
}

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

    int nodes, edges;
    fin >> nodes >> edges;

    auto adjList = readAdjacencyListWeighted(fin, nodes, edges);

    auto dst = dijkstra(adjList, 1);

    for (int i = 2; i <= nodes; i++) {
        fout << dst[i] << " ";
    }
    fout << endl;

    fin.close();
    fout.close();

    return 0;
}