#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];
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;
    dp[start] = 0;
    bool ok = false;
    q.push(start);
    while(!q.empty() && ok == false)
    {
       start = q.front();
       q.pop();

       for(i=0; i < g[start].size(); i++)
       {
          int u = g[start][i].nod;
          int c = g[start][i].cost;
          if(1ll*dp[u] > 1ll * dp[start] + c)
          {
              if(visited[u] == 1)
              {
                  ok = true;
                  break;
              }
              visited[u] = 1;
              dp[u] = dp[start] + c;
              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;
}