/**
  *  Worg
  */
#include <queue>
#include <vector>
#include <cstdio>

using std::vector;
using std::priority_queue;

FILE *fin = freopen("dijkstra.in", "r", stdin);
FILE *fout = freopen("dijkstra.out", "w", stdout);

const int kMaxN = 1 + 50000;  //  Numarul maxim de noduri
const int kMaxInf = 2000000000;  //  Infinit

/*-------- Structures --------*/
struct Edge {
    int node, dist;
    Edge(const int _node, const int _dist) {
        this->node = _node; this->dist = _dist;
    }
    bool operator <(const Edge &other) const {  ///  Operatorul de comparatie pentru std::priority_queue.
        return this->dist > other.dist;  ///  Datorita implementarii de la std::priority_queue, semnul se pune invers.
    }
};
/*-------- Input data --------*/
int N, M;
vector<Edge > graph[kMaxN];
/*-------- Dijkstra --------*/
int min_dist[kMaxN];
priority_queue<Edge > heap;
/*-------- --------*/

void ReadInput() {
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++) {
        int u, v, dist; scanf("%d%d%d", &u, &v, &dist);
        graph[u].push_back(Edge(v, dist));
    }
}

void DijkstraAlgorithm() {
    for(int i = 1; i <= N; i++) {
        min_dist[i] = kMaxInf;
    }

    heap.push(Edge(1, 0));  //  Adaugam sursa, adica nodul 1, cu distanta 0
    while(!heap.empty()) {
        Edge edge = heap.top(); heap.pop();

        if(min_dist[edge.node] == kMaxInf) {  //  Daca distanta pana la nod nu e deja calculata, inseamna ca i-o atribuim pe cea curenta.
            min_dist[edge.node] = edge.dist;
            for(Edge next_edge : graph[edge.node]) {  //  Ne uitam la muchiile care ies din nodul curent
                if(min_dist[next_edge.node] == kMaxInf) {  //  Daca dam peste un vecin a carui distanta nu a fost calculata, adaugam in heap perechea
                    heap.push(Edge(next_edge.node, edge.dist + next_edge.dist));
                }
            }
        }
    }
}

void WriteOutput() {
    for(int i = 2; i <= N; i++) {
        printf("%d ", min_dist[i]);
    }
}

int main() {
    ReadInput();
    DijkstraAlgorithm();
    WriteOutput();
    return 0;
}