#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;

inline void swap(int &x, int &y){
    x ^= y ^= x ^= y;
}

void ascend(int p){
    int ax;
    while(p != 1 && dp[heap[p]] < dp[heap[p>>1]]){
        swap(pos[heap[p]], pos[heap[p>>1]]);
        swap(heap[p], heap[p>>1]);
        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){
            swap(pos[heap[p<<1]], pos[heap[p]]);
            swap(heap[p<<1], heap[p]);
            p = p<<1;
        }else{
            if(mn2 == INF){
                break;
            }
            swap(pos[heap[(p<<1)+1]], pos[heap[p]]);
            swap(heap[(p<<1)+1], heap[p]);
            p = (p<<1)+1;
        }
    }
    swap(pos[heap[ch]], pos[heap[p]]);
    swap(heap[p], heap[ch]);
    pos[heap[ch]] = 0;
    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;
    pos[1] = 1;
    int id;
    while(ch){
        id = heap[1];
        vis[id] = 1;
        descend(pos[id]);
        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]);
            }
        }
    }
    for(i = 2;i <= n;i++){
        printf("%d ",(dp[i] == INF ? 0 : dp[i]));
    }
    return 0;
}