#include <fstream>
#include <cstring>
#include <queue>
#include <vector>

#define max_n 50001
#define nod first
#define cost second
#define INF 0x3f3f3f3f

using namespace std;

int n,m,i,j,x,y,z,c;
vector < pair < int, int> > g[max_n];
vector < pair < int, int> >::iterator it;
queue <int> q;
bool ok[max_n];
int d[max_n],nr[max_n];


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

int main () {
    in >> n >> m;
    for (i=1; i<=m; i++) {
        in >> x >> y >> z;
        g[x].push_back(make_pair(y,z));
    }

    memset(d,INF,sizeof(d));
    memset(ok,false,sizeof(ok));
    memset(nr,0,sizeof(nr));
    ok[1]=true;
    d[1]=0;
    q.push(1);

    while (!q.empty()) {
           i=q.front();
           q.pop();
           ok[i]=false;
           for (it=g[i].begin(); it!=g[i].end(); it++){
               j=(*it).nod;
               c=(*it).cost;
               if (d[j]>d[i]+c) {
                        d[j]=d[i]+c;
               if (!ok[j]) {
                   q.push(j);
                   ok[j]=true;
                   nr[j]++;
                   if (nr[j]>n) {
                      out << "Ciclu negativ!";
                      return 0;
                  }
               }
               }
           }
    }

    for (i=2; i<=n; i++)
        out << d[i] <<  ' ';
    return 0;
}