#include <bits/stdc++.h>

using namespace std;

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

//vector <pair<int, pair<int, int>>> muchii[250005];
set <pair<int, int>> g[50005];
int dist[50005];
int optimizat[50005];
int n, m;
int bellman (int src)
{
    dist[src]=0;
    queue <pair<int, int>> cheap_nod;
    cheap_nod.push({0, src});
    while (!cheap_nod.empty()) {
        int nod=cheap_nod.front().second;
        cheap_nod.pop();
        for (pair <int, int> muchie: g[nod]) {
            int dest=muchie.second;
            int cost=muchie.first;
            if (dist[nod]+cost<dist[dest]) {
                dist[dest]=dist[nod]+cost;
                cheap_nod.push({dist[dest], dest});
                optimizat[dest]++;
                if (optimizat[dest]==n+1) {
                    return -1;
                }
            }
        }
    }
    return 1;
}

int main()
{
    int x, y, z;
    fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>x>>y>>z;
        g[x].insert({z, y});
    }
    for (int i=1; i<=n; i++) {
        dist[i]=1000000005;
    }
    int rez=bellman(1);
    if (rez==-1) {
        fout<<"Ciclu negativ!";
        return 0;
    }
    for (int i=2; i<=n; i++) {
        fout<<dist[i]<<' ';
    }
    return 0;
}