/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   main.cpp
 * Author: octavian
 *
 * Created on 05 October 2016, 14:33
 */

#include <cstdlib>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;


const int NMAX = 50005;
const int INF = 1000000005;

int N, M;

typedef struct {
    int destination;
    int cost;
} Edge;

vector<Edge> graph[NMAX];
int dist[NMAX];

/*
 *
 */
int main(int argc, char** argv) {

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

    fprintf(fout, "starting to read input file");

    fscanf(fin, "%d %d", &N, &M);
    for(int i = 1 ; i <= M ; i++) {
        int a, b, c;
        fscanf(fin, "%d %d %d", &a, &b, &c);
        fprintf(fout, "read %d %d %d\n", a, b, c);
        Edge edge = {b, c};
        graph[a].push_back(edge);
    }

    for(int i = 2 ; i <= N ; i++) {
        dist[i] = INF;
    }

    priority_queue<int> qu;

    qu.push(1);
    while(!qu.empty()) {
        int top = qu.top();
        qu.pop();
        for(int i = 0 ; i < graph[top].size() ; i++) {
            int vertex = graph[top][i].destination;
            int cost = graph[top][i].cost;
            if(dist[vertex] > dist[top] + cost) {
                dist[vertex] = dist[top] + cost;
                qu.push(vertex);
            }
        }
    }

    for(int i = 2 ; i <= N ; i++) {
        fprintf(fout, "%d ", dist[i]);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}