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

int n, m;
vector<pair<long long,long long >> lista[MAXN];
vector<pair<long long,long long >> heap;
long long poz[MAXN];
long long tata[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;
    pair<int,double> aux;

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

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

        i = i / 2;
    }
}

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

    int i = x;
    int aux1;
    pair<int,double> aux;

    while((heap[i].second > heap[i * 2].second && i * 2 <= k) || (heap[i].second > heap[i * 2 + 1].second && (i * 2 + 1) <= k)){
            if(heap[2 * i] > heap[2 * i + 1] && 2 * i + 1 <= k){
                aux1 = poz[heap[2 * i + 1].first];
                poz[heap[2 * i + 1].first] = poz[heap[i].first];
                poz[heap[i].first] = 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].first];
                poz[heap[2 * i].first] = poz[heap[i].first];
                poz[heap[i].first] = aux1;

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

void solve(){

    int i, node = 0;
    long long value = 0;

    for(i = 1;i <= n; ++i){
        poz[i] = i;
    }

    heap.push_back(make_pair(0,0));
    heap.push_back(make_pair(1,0));

    for(i = 2;i <= n; ++i)
        heap.push_back(make_pair(i,INF));


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

        tata[heap[1].first] = node;
        node = heap[1].first;
        value = heap[1].second;

        //cout << node << " " << value << endl;

        poz[node] = n - i + 1;
        heap[1] = heap[n - i + 1];
        heap[n - i + 1] = make_pair(node,value);
        poz[heap[1].first] = 1;
        heapDown(1,n - i);


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

        for(int j = 0;j < len; ++j)
            if(poz[lista[node][j].first] > 0)
                heap[poz[lista[node][j].first]].second = min(heap[poz[lista[node][j].first]].second,
                                                             value + lista[node][j].second);

        for(int j = 1;j <= n - i; ++j)
            heapDown(j,n - i);
    }
}


void print(){

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

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

int main(){

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