#include <fstream>
#include <vector>
#include <utility>
#include <climits>

using std::vector;

struct Node{
    vector<std::pair<int, int>> edges;
    int pred, nrEdges;
    Node(){ 
        pred = 0;
        nrEdges = 0;
    }
    void addEdge(std::pair<int, int> x){
        edges.push_back(x);
        nrEdges++;
    }
};

int main(){
    std::ifstream bem("bellmanford.in");
    std::ofstream kim("bellmanford.out");
    int n, m;
    bem >> n >> m;
    vector<Node> nodes(n);
    vector<int> dist(n, INT_MAX);
    dist[0] = 0;
    for(int i = 0; i < m; i++){
        int x, y, cost;
        bem >> x >> y >> cost;
        x--;
        y--;
        nodes[x].addEdge({y, cost});
    }
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < nodes[i].nrEdges; j++)
            if(dist[i] + nodes[i].edges[j].second < dist[nodes[i].edges[j].first]){
                dist[nodes[i].edges[j].first] = dist[i] + nodes[i].edges[j].second;
                nodes[j].pred = i;
            }
    for(int i = 1; i < n; i++)
        kim << dist[i] << ' ';
    return 0;
}