#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 60050
#define INF 0x3f3f3f3f
using namespace std;

int n, m;
vector<pair<int,int >> lista[MAXN];
vector<int> heap;
int poz[MAXN];
int tata[MAXN];
int dist[MAXN];

void read(){

    fstream f("dijkstra.in",ios::in);

    f >> n >> m;
    int i, a, b, c;

    while(f >> a >> b >> c)
        lista[a].push_back(make_pair(b,c));
}

void heapUp(int k){

    int i = k;
    int aux1;
    int aux;

    while(dist[heap[i]] < dist[heap[i / 2]] && i > 1){
        aux = heap[i];
        heap[i] = heap[i / 2];
        heap[i / 2] = aux;

        aux1 = poz[heap[i]];
        poz[heap[i]] = poz[heap[i / 2]];
        poz[heap[i / 2]] = aux1;

        i = i / 1;
    }
}

void heapDown(int x,int k){ //pozitia din heap care trebuie updata si numarul de elemente din heap

    int i = x;
    int aux1;
    int aux;

    while((dist[heap[i]] > dist[heap[i * 2]] && i * 2 <= k) || (dist[heap[i]] > dist[heap[i * 2 + 1]] && (i * 2 + 1) <= k)){
         if(dist[heap[2 * i]] > dist[heap[2 * i + 1]] && 2 * i + 1 <= k){
                aux1 = poz[heap[2 * i + 1]];
                poz[heap[2 * i + 1]] = poz[heap[i]];
                poz[heap[i]] = aux1;

                aux = heap[2 * i + 1];
                heap[2 * i + 1] = heap[i];
                heap[i] = aux;

                i = i * 2 + 1;
            }
            else{
                aux1 = poz[heap[2 * i]];
                poz[heap[2 * i]] = poz[heap[i]];
                poz[heap[i]] = aux1;

                aux = heap[2 * i];
                heap[2 * i] = heap[i];
                heap[i] = aux;
                i = i * 2;
            }
    }
}

void solve(){

    int i, node = 0;
    int value = 0;
    int heap_size = 1;

    heap.push_back(-1);

    for(i = 1;i <= n; ++i){
        poz[i] = -1;
        dist[i] = INF;
        heap.push_back(i);
    }

    dist[1] = 0;
    poz[1] = 1;

    for(int i = 1;i < n; ++i){

        tata[heap[1]] = node;
        node = heap[1];
        value = dist[node];

        heap[1] = heap[heap_size];
        heap[heap_size] = node;
        poz[heap[1]] = 1;
        poz[node] = heap_size;

        --heap_size;
        heapDown(1,heap_size);

        int len = lista[node].size();

        for(int j = 0;j < len; ++j){
            int nod_list = lista[node][j].first;
            int val_list = lista[node][j].second;

            if(dist[nod_list] > val_list + value){
                dist[nod_list] = val_list + value;

                if(poz[nod_list] == -1){
                    ++heap_size;
                    heap[heap_size] = nod_list;
                    poz[nod_list] = heap_size;
                    heapUp(heap_size);
                }
                else
                    heapUp(poz[nod_list]);
            }
        }
    }
}


void print(){

    fstream g("dijkstra.out",ios::out);

    for(int i = 2;i <= n; ++i)
        if(dist[i] == INF)
            g << 0 << " ";
        else
            g << dist[i] << " ";
}

int main(){

    read();
    solve();
    print();
    return 0;
}