#include <bits/stdc++.h>
#define MAX 131072

using namespace std;
const int NMAX = 50010;
const int EMAX = 250010;

FILE *IN;

struct edge{
    int x, cost;
};
vector <edge> edges[EMAX];

int N, M, heapSize;
int poz[NMAX], val[NMAX], st[NMAX], heap[NMAX];
int ans[NMAX];
bool use[NMAX], add[NMAX];

int pos, sign;
char f[MAX];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign = 1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

void read(){
    Read(N); Read(M);
    int X, Y, Cost;
    for(int i = 1; i <= M; i++){
        Read(X); Read(Y); Read(Cost);
        edges[X].push_back({Y, Cost});
    }
}

inline void Swap(int x, int y){
    swap(heap[x], heap[y]);
    poz[heap[x]] = x;
    poz[heap[y]] = y;
}

void upHeap(int node){
    int s = node / 2;
    if(val[heap[node]] < val[heap[s]] && node > 1){
        Swap(node, s);
        upHeap(s);
    }
}

void downHeap(int node){
    int s = 2 * node;
    if(s > heapSize)
        return;
    if(s < heapSize && val[heap[s]] > val[heap[s + 1]]) s++;
    if(val[heap[node]] > val[heap[s]]){
        Swap(node, s);
        downHeap(s);
    }
}

int main(){

    IN = fopen("dijkstra.in", "r");
    freopen("dijkstra.out", "w", stdout);

    read();
    for(int i = 1; i <= N; i++)
        val[i] = 2e9;

    int Min, node, nrNodes = 0;
    for(int i = 1; i <= N; i++){
        if(heapSize > 0){
            node = heap[1];
            Min = val[node];
            Swap(1, heapSize);
            heapSize--;
            downHeap(1);
            poz[node] = 0;
            val[node] = 2e9;
        } else Min = 0, node = 1;

        use[node] = true;
        ans[node] = Min;
        for(int j = 0; j < edges[node].size(); j++){
            int Cost = edges[node][j].cost;
            int Nd = edges[node][j].x;
            if(!add[edges[node][j].x]){
                heapSize++;
                heap[heapSize] = edges[node][j].x;
                val[heap[heapSize]] = ans[node] + edges[node][j].cost;
                poz[heap[heapSize]] = heapSize;
                add[heap[heapSize]] = true;
                upHeap(heapSize);
            } else if(!use[edges[node][j].x] && val[edges[node][j].x] > ans[node] + edges[node][j].cost){
                val[edges[node][j].x] = ans[node] + edges[node][j].cost;
                upHeap(poz[edges[node][j].x]);
            }
        }
    }

    for(int i = 2; i <= N; i++)
        printf("%d ", ans[i]);


    return 0;
}

//-41801