#include <bits/stdc++.h>
using namespace std;

ifstream f("bellmanfor1.in");
ofstream g("bellmanford1.out");

int n,m;
vector<vector<pair<int,int>>> v;
vector<int> dist;
vector<int> cnt;
queue<int> coada;

void Read()
{
    f>>n>>m;
    v.resize(m+1);
    dist.resize(n+1,INT_MAX);
    cnt.resize(n+1);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        v[x].emplace_back(y,c);
    }
    f.close();
}

void Bellman(int nodStart)
{
   dist[nodStart]=0;
   coada.push(nodStart);
   while(!coada.empty())
   {
       int nod=coada.front();
       coada.pop();
       if(++cnt[nod] > n)
       {
           g<<"Ciclu negativ!";
           g.close();
           return;
       }
       for(auto arc : v[nod])
       {
           if(dist[nod] + arc.second < dist[arc.first])
           {
               dist[arc.first] = dist[nod] + arc.second;
               coada.push(arc.first);
           }
       }
   }
   for(int i=2;i<=n;i++)
        g<<dist[i]<<" ";
   g.close();
}


int main()
{
    Read();
    Bellman(1);
    return 0;
}