#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;
    Node * nodes = new Node[n];
    int * dist = new int[n];
    for(int i = 0; i < m; i++){
        int x, y, cost;
        bem >> x >> y >> cost;
        x--;
        y--;
        nodes[x].addEdge({y, cost});
        dist[i] = INT_MAX;
    }
    dist[0] = 0;

    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 = 0; i < n; i++)
        kim << dist[i] << ' ';
    delete [] dist;
    delete [] nodes;
}