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

using std::vector;

struct Node{
    int nrEdges, pred, dist;
    vector<std::pair<int, int>> edges;
    Node(){
        dist = INT_MAX;
        pred = -1;
        nrEdges = 0;
        edges.resize(0);
    }
    void addEdge(int edge, int cost){
        nrEdges++;
        edges.push_back({edge, cost});
    }
};

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