/*
 * 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: daniel
 *
 * 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;

struct Edge{
    int destination;
    int cost;
};

int dist[NMAX];

struct Node{
    int node;
    int currentValue;
};


struct comp {
    bool operator()(const Node &n1, const Node &n2) const
    {
        return n1.currentValue < n2.currentValue;
    }
};

vector<Edge> graph[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<Node, vector<Node>, comp> qu;

    Node firstNode = {1, 0};
    qu.push(firstNode);

    while(!qu.empty()) {
        Node top = qu.top();
        int topNode = top.node;
        int value = top.currentValue;
        qu.pop();

//        fprintf(fout, "topNode: %d\n", topNode);
//        fprintf(fout, "value: %d\n", value);

        if(value <= dist[topNode]) {
            for(int i = 0 ; i < graph[topNode].size() ; i++) {
                int vertex = graph[topNode][i].destination;
                int cost = graph[topNode][i].cost;
                if(dist[vertex] > dist[topNode] + cost) {
                    dist[vertex] = dist[topNode] + cost;
                    Node node = {vertex, dist[vertex]};
                    qu.push(node);
                }
            }
        }
    }

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

    fclose(fin);
    fclose(fout);

    return 0;
}