#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int NMAX = 500000;
const int INF = INT_MAX;
struct muchie{
    int nod, cost;
};
vector<muchie>g[NMAX+5];
bitset<NMAX+5>in_queue;
vector<int>cnt_in_queue;
queue <int> q;
int dp[NMAX+5];
bool visited[NMAX+5];
void bellmanFord(int start, int n)
{
    int i;
    visited[start] = 1;
    int cnt = 1;
    for(i=1;i<=n;i++)
        {
            dp[i] = INF;
            cnt_in_queue.push_back(0);

        }
    dp[start] = 0;
    bool ok = false;
    q.push(start);
    in_queue[start] = true;
    while(!q.empty() && ok == false)
    {
       start = q.front();
       in_queue[start] = false;
       q.pop();

       for(i=0; i < g[start].size(); i++)
       {
          int u = g[start][i].nod;
          int c = g[start][i].cost;
          if(dp[u] > dp[start] + c)
          {
              dp[u] = dp[start] + c;
              if(in_queue[u]== false)
              {
                  if(cnt_in_queue[u] > n)
                  {
                      ok = true;
                      break;
                  }
                  cnt_in_queue[u]++;
                  in_queue[u] = true;
                  q.push(u);
              }

          }
       }
    }
    if(ok == false)
    {
       for(i=2;i<=n;i++)
        fout<<dp[i]<<" ";
       fout<<"\n";
    }
    else{
        fout<<"Ciclu negativ!"<<"\n";
    }

}



int main()
{
    int n, m, i, a, b, c;
    muchie aux;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
       fin>>a>>b>>c;
       aux.nod = b;
       aux.cost = c;
       g[a].push_back(aux);
    }
    bellmanFord(1,n);

    return 0;
}