#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f

std::ifstream fin("bellmanford.in");
std::ofstream fout("bellmanford.out");


class Graph{
    int V;
    std::vector<int>cost_minim;
    std::vector<int>frec;
    std::vector<std::vector<std::pair<int, int>>>adj;
public:
    Graph(int v) {
        V = v;
        cost_minim.resize(V+1, INF);
        frec.resize(V+1);
        adj.resize(V+1);
    }
    void addEdge(int x, int y, int z) {
        adj[x].push_back({y, z});
    }

    void bellmanFord(int src) {
        std::queue<int>q;
        cost_minim[src] = 0;

        q.push(src);

        while(!q.empty()) {
            int c = q.front();
            frec[c]++;
            if(frec[c] >= V+1) { fout << "Ciclu negativ!"; return; }
            q.pop();

            for(const std::pair<int, int>& vec : adj[c]) {
                int dst = vec.first; int cost = vec.second;

                if(cost_minim[dst] > cost_minim[c] + cost) {
                    cost_minim[dst] = cost_minim[c] + cost;
                    q.push(dst);
                }
            }
        }

        for(int i=2;i<=V;++i)  fout << cost_minim[i] << " "; 

    }
};


int main(void) {
    int n, m, x, y, z;


    fin >> n >> m;
    Graph g(n);
    
    for(int i=1;i<=m;++i) {
        fin >> x >> y >> z;
        g.addEdge(x, y, z);
    }
    g.bellmanFord(1);

    return 0;
}