#include<stdio.h>
#include<queue>

using namespace std;

#define INF 1000000005
#define NMAX 300005

priority_queue< pair<int,int> > myheap; 
vector< pair<int, int> > graph[NMAX];

int n, m, dist[NMAX];
bool viz[NMAX];

int main() {
    int a, b, c;
 
    freopen("dijkstra.in", "r",stdin);
    freopen("dijkstra.out", "w", stdout);
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        graph[a].push_back(make_pair(b, c));
    }
    
    myheap.push(make_pair(0, 1));
    dist[1] = 0;
    for(int i = 2; i <= n; i++) {
        dist[i] = INF;
        viz[i] = false;
    }
    
    while(!myheap.empty()) {
        pair<int, int> best = myheap.top();
        myheap.pop();
        //printf("Am selectat perechea %d %d\n", best.first, best.second);
        
        int current_node = best.second;
        if(viz[current_node]) {
            continue;
        }
        viz[current_node] = true;
        
        for(auto edge : graph[current_node]) {
            int neight = edge.first;
            int cost = edge.second;
//            printf("Vecin %d %d\n", neight, cost);
            if(dist[neight] > dist[current_node] + cost) {
                dist[neight] = dist[current_node] + cost;
                myheap.push(make_pair(-dist[neight], neight));
            }
        }
    }
    
    for(int i = 2; i <= n; i++) {
        if(dist[i] == INF) {
            printf("0 ");
        }
        else {
            printf("%d ", dist[i]);
        }
    }
    printf("\n");
    
    return 0;
}