#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
 
int n, m, d[50001], a, b, c, l, viz[50001];
bool inCoada[50001];
#define INF 100000000
 
vector < pair <int, int> > g[50001];
 
struct cmp {
   bool operator ()(int a, int b) {
        return d[a] > d[b];
   }
};
 
priority_queue<int, vector<int>, cmp> q;
 
void Citire() {
     fin >> n >> m;
     for (int i=1;i<=m;i++) {
        fin >> a >> b >> c;
        g[a].push_back(make_pair(b,c));
     }
}
 
int Bellman_Ford (int nodStart) {
       for (int i=2;i<=n;i++) d[i] = INF;
       d[nodStart] = 0;
       q.push(nodStart);
       inCoada[nodStart] = 1;
       while (!q.empty()) {
            int nodCurent = q.top();
            viz[nodCurent]++;
            if (viz[nodCurent]>=n) return 0;
            q.pop();
            inCoada[nodCurent] = 0;
            for (int i=0;i<g[nodCurent].size();i++) {
                int Vecin = g[nodCurent][i].first;
                int Cost = g[nodCurent][i].second;
                if (d[nodCurent]+Cost<d[Vecin]) {
                    d[Vecin] = d[nodCurent]+Cost;
                    if (inCoada[Vecin]==0) {
                        q.push(Vecin);
                        inCoada[Vecin] = 1;
                    }
                }
            }
       }
       return 1;
}
 
void Afisare() {
       for (int i=2;i<=n;i++)
            if (d[i]==INF) fout <<-1 << " ";
            else fout << d[i] << " ";
}
 
int main()
{
    Citire();
    if (Bellman_Ford(1)) Afisare();
    else fout << "Ciclu negativ!";
    return 0;
}