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

using namespace std;
ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");
const int nmax=5e4, inf=2e9;
int n, m, cNeg;
int dst[nmax+5], updated[nmax+5];
vector <pair <int, int> > G[nmax+5];
queue <int> Q;

void bFord(void)
{
    dst[1]=0;
    for(int i=2; i<=n; i++)
        dst[i]=inf;
    Q.push(1);
    while(!Q.empty())
    {
        int nod=Q.front();
        Q.pop();
        for(auto vec:G[nod])
        {
            int nods=vec.second;
            int cost=vec.first;
            if(dst[nods]>dst[nod]+cost)
            {
                dst[nods]=dst[nod]+cost;
                Q.push(nods);
                updated[nods]++;
                if(updated[nods]>n-1)
                {
                    cNeg=1;
                    return;
                }
            }
        }
    }
}

int main()
{
    fi>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x, y, c;
        fi>>x>>y>>c;
        G[x].push_back({c, y});
    }
    bFord();
    if(cNeg)
        fo<<"Ciclu negativ!";
    else
        for(int i=2; i<=n; i++)
            fo<<dst[i]<<" ";
    fi.close();
    fo.close();
    return 0;
}