#include<iostream>
#include <stdio.h>
#include <vector> 
#include <map>
#include <string.h>
#include <set>

using namespace std;

#define INF 1000000001

struct Neighbor {
    int v;
    int cost;

    Neighbor(int x, int c) : v(x), cost(c) {
    }
};

struct Node {
    int u; 
    int dist; 
    Node(int x, int d) : u(x), dist(d) {
    }

    bool operator<(const Node& lhs) const {
        if ( dist == lhs.dist) 
            return u < lhs.u;
        return dist < lhs.dist;
    }
    
};

void computeSSSP(map<int, vector<Neighbor> >& graph, int distance[], int N) {
    set<Node> pq;
    pq.insert(Node(1, 0));
    for (int i = 2; i <= N; i++) {
        pq.insert(Node(i, INF));
    }

    while (pq.empty() == false) {
        Node currNode = *(pq.begin());
        vector<Neighbor> children = graph[currNode.u]; 
 
        for (int i = 0; i < children.size(); i++) {
            Neighbor child = children[i];
            int newDist = currNode.dist + child.cost; 
            if (distance[child.v] > newDist) {
                set<Node>::iterator it = pq.find(Node(child.v, distance[child.v])); 
                pq.erase(it); 
                distance[child.v] = newDist; 
                pq.insert(Node(child.v, newDist)); 
            }
        }
        pq.erase(currNode); 
    }

}

int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int N, M;
    cin >> N >> M;
    map<int, vector<Neighbor> > graph;
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        graph[u].push_back(Neighbor(v, c));
    }
    int distance[N + 1];
    for (int i = 1; i <= N; i++) {
        distance[i] = INF;
    }
    distance[1] = 0;
    
    computeSSSP(graph, distance, N); 
    for (int i = 2; i <= N; i++) {
        cout << distance[i]; 
        if ( i < N) {
            cout << " "; 
        }
    }
    cout << endl; 
    fclose(stdout);
    
    return 0;
}