/*
 * 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 <cstdio>
#include <set>
#include <iostream>
#include <fstream>

using namespace std;


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

int N, M;

struct Edge{
    int destination;
    int cost;
};

int dist[NMAX];

ifstream fin("dijkstra.in");

//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];

vector<int> heap;
int posInHeap[NMAX];

void swap(int &a, int &b) {
    int interim = a;
    a = b;
    b = interim;
}

void insert(int vertex, FILE* fout) {
    heap[++heap[0]] = vertex;
    posInHeap[vertex] = heap[0];

//    fprintf(fout, "vertex: %d\n", vertex);
//    fflush(fout);
//
//
//    fprintf(fout, "before insert\n");
//    for(int i = 0 ; i <= heap[0] ; i++) {
//        fprintf(fout, "%d ", heap[i]);
//    }
//    fprintf(fout, "\n");

    while(posInHeap[vertex] / 2 && dist[heap[posInHeap[vertex] / 2]] > dist[heap[posInHeap[vertex]]]) {
        int son = vertex;
        int father = heap[posInHeap[vertex] / 2];
//        fprintf(fout, "posInHeap[vertex]: %d, posInHeap[vertex]/2: %d ", posInHeap[vertex], posInHeap[vertex] / 2);
        swap(heap[posInHeap[vertex] / 2], heap[posInHeap[vertex]]);
        swap(posInHeap[son], posInHeap[father]);
        vertex = father;
    }

//    fprintf(fout, "after insert\n");
//    for(int i = 0 ; i <= heap[0] ; i++) {
//        fprintf(fout, "%d ", heap[i]);
//    }
//    fprintf(fout, "\n");
}

int remove(int position, FILE* fout) {
//    fprintf(fout, "position: %d\n", position);
//    fflush(fout);

    int removedValue = heap[position];

//    fprintf(fout, "removed value: %d, position: %d\n", removedValue, position);
//
//    fprintf(fout, "before remove\n");
//    for(int i = 0 ; i <= heap[0] ; i++) {
//        fprintf(fout, "%d ", heap[i]);
//    }
//    fprintf(fout, "\n");


    while(position*2 <= heap[0]) {
        if(position*2 + 1 <= heap[0] && dist[heap[position*2 + 1]] < dist[heap[position*2]]) {
            heap[position] = heap[position*2 + 1];
            posInHeap[heap[position]] = position;
            position = (position*2)+1;
        }
        else {
            heap[position] = heap[position*2];
            posInHeap[heap[position]] = position;
            position = (position*2);
        }
//        fprintf(fout, "posInHeap of %d becomes %d\n", heap[position], position);
    }

    posInHeap[heap[heap[0]]] = position;
    heap[position] = heap[heap[0]];
    posInHeap[removedValue] = 0;
    heap[heap[0]] = 0;
    heap[0]--;

//    fprintf(fout, "after remove\n");
//    for(int i = 0 ; i <= heap[0] ; i++) {
//        fprintf(fout, "%d ", heap[i]);
//    }
//    fprintf(fout, "\n");


    return removedValue;
}



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

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

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

    fin >> N >> M;

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

    for(int i = 2 ; i <= N ; i++) {
        dist[i] = INF;
    }
//
//    set<Node, vector<Node>, comp> pq;
//
//    Node firstNode = {1, 0};
//    pq.insert(firstNode);

//    fprintf(fout, "inserting\n");
//    fflush(fout);

    heap.resize(NMAX * sizeof(int));
    insert(1, fout);

    while(heap[0]) {
        int topNode = remove(1, fout);//remove the top element

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

        for(int i = 0 ; i < graph[topNode].size() ; i++) {
            int vertex = graph[topNode][i].destination;
            int cost = graph[topNode][i].cost;
//            fprintf(fout, "destination: %d\n", vertex);

            if(dist[vertex] > dist[topNode] + cost) {
                if(posInHeap[vertex]) {
                    remove(posInHeap[vertex], fout);
//                    fprintf(fout, "posInHeap[vertex]: %d\n", posInHeap[vertex]);
                }
                dist[vertex] = dist[topNode] + cost;
                insert(vertex, fout);
            }
        }
//        fprintf(fout, "dist[13]: %d\n", dist[13]);
//        fprintf(fout, "posInHeap[602]: %d\n", posInHeap[602]);
    }

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

    fclose(fout);

    return 0;
}