#include <bits/stdc++.h>
#define INF 999999999
#define NMAX 50005

using namespace std;

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

struct muchie{
    int dest;
    int cost;
    friend bool operator >(muchie a, muchie b);
};
muchie aux, nou;

bool operator >(muchie a, muchie b){
    if(a.cost < b.cost)
        return 0;
    return 1;
}

priority_queue<muchie, vector<muchie>, greater<muchie> > Heap;
vector<int> vecini[NMAX], costuri[NMAX];

int n, m, i, x, y, z, cmin[NMAX], uz[NMAX];

int main(){
    cin >> n >> m;
    for(i=1; i<=m; ++i){
        fscanf(fin, "%d%d%d", &x, &y, &z);
        aux.dest = y;
        aux.cost = z;
        vecini[x].push_back(y);
        costuri[x].push_back(z);
        Heap.push(aux);
        }
    for(i=2; i<=m; ++i)
        cmin[i] = INF;
    for(i=0; i<vecini[1].size(); ++i)
        cmin[vecini[1][i]] = costuri[1][i];
    cmin[1] = 0;
    uz[1] = 1;
    while(!Heap.empty()){
        aux = Heap.top();
        Heap.pop();
        if(uz[aux.dest] == 0){
            uz[aux.dest] = 1;
            for(i=0; i<vecini[aux.dest].size(); ++i){
                if(cmin[aux.dest] + costuri[aux.dest][i] < cmin[vecini[aux.dest][i]]){
                    cmin[vecini[aux.dest][i]] = cmin[aux.dest] + costuri[aux.dest][i];
                    nou.dest = vecini[aux.dest][i];
                    nou.cost = cmin[vecini[aux.dest][i]];
                    Heap.push(nou);
                    }
                }
            }
        }
    for(i=2; i<=n; ++i)
        fprintf(fout, "%d ", cmin[i]);
    return 0;
}