#include <cstdio>
#include <vector>
using namespace std;

vector < pair <int, int> > v[50005];
int dp[50005], heap[50005], pos[50005], ch;
bool vis[50005];
const int INF = 1<<30;

void ascend(int p){
    int ax;
    while(p != 1 && dp[heap[p]] < dp[heap[p>>1]]){
        pos[heap[p]] = p>>1;
        pos[heap[p>>1]] = p;
        ax = heap[p];
        heap[p] = heap[p>>1];
        heap[p>>1] = ax;
        p >>= 1;
    }
}

void descend(int p){
    int mn1, mn2;
    while(p <= ch){
        mn1 = INF;
        mn2 = INF;
        if((p<<1) <= ch){
            mn1 = dp[heap[p<<1]];
        }
        if((p<<1)+1 <= ch){
            mn2 = dp[heap[(p<<1)+1]];
        }
        if(mn1 < mn2){
            heap[p] = heap[p<<1];
            pos[heap[p<<1]] = p;
            p = p<<1;
        }else{
            if(mn2 == INF){
                break;
            }
            heap[p] = heap[(p<<1)+1];
            pos[heap[(p<<1)+1]] = p;
            p = (p<<1)+1;
        }
    }
    heap[p] = heap[ch];
    pos[heap[ch]] = p;
    heap[ch] = 0;
    ch--;
}

int main(){
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int n,m,i,x,y,c;
    scanf("%d %d", &n, &m);
    for(i = 1;i <= m;i++){
        scanf("%d %d %d", &x, &y, &c);
        v[x].push_back({y, c});
    }
    dp[0] = INF;
    for(i = 2;i <= n;i++){
        dp[i] = INF;
    }
    heap[++ch] = 1;
    int id;
    int all = n-1;
    while(ch){
        id = heap[1];
        vis[id] = 1;
        for(auto it : v[id]){
            if(vis[it.first] == false && dp[it.first] > dp[id] + it.second){
                dp[it.first] = dp[id] + it.second;
                if(pos[it.first] == 0){
                    heap[++ch] = it.first;
                    pos[it.first] = ch;
                }
                ascend(pos[it.first]);
            }
        }
        heap[1] = 0;
        descend(1);
    }
    for(i = 2;i <= n;i++){
        printf("%d ",dp[i]);
    }
    return 0;
}