#include<iostream>
#include <stdio.h>
#include <vector> 
#include <map>
#include <string.h>

using namespace std;

#define INF 1000000001

struct Neighbor{
    int v;
    int cost;
    Neighbor(int x, int c): v(x), cost(c) {}   
};

void computeSSSD(int distance[],int N, map<int, vector<Neighbor> >& graph) {
 
    for (int i = 0; i < N - 1; i++) {
       map<int, vector<Neighbor> >::iterator git = graph.begin();
        for (; git != graph.end(); ++git) {
            int u = git->first;
            vector<Neighbor> neigh = git->second;
            for (int j = 0; j < neigh.size(); j++) {   
                int v = neigh[j].v;
                if (distance[u] + neigh[j].cost < distance[v]) {
                    distance[v] = distance[u] + neigh[j].cost;
                }
            }    
        }
    }
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    
    int N, M;
    cin >> N >> M;
    map<int, vector<Neighbor> > graph;
    for (int i = 0 ; i < M; i++) {
        int u, v, c; 
        cin >> u >> v >> c;
        graph[u].push_back(Neighbor(v, c));
    }
    int distance[N + 1];
    for (int i = 1; i <= N; i++){
        distance[i] = INF;
    }
    distance[1] = 0;
    computeSSSD(distance, N, graph);
    for(int i = 2; i <= N; i++) {
        cout << distance[i];
        if (i <= N - 1) {
            cout << " ";                
        }
    }
    cout << endl;
   
    fclose(stdout);
    return 0;
     
}