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

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, 1001);
    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});
    }
    dist[0] = 0;
    
    for(int k = 0; k < n - 1; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < nodes[i].nrEdges; j++)
                dist[nodes[i].edges[j].first] = std::min(
                    dist[i] + nodes[i].edges[j].second,
                    dist[nodes[i].edges[j].first]
                );
    for(int i = 1; i < n; i++)
        kim << dist[i] << ' ';
    return 0;
}