#include <fstream>
#include <vector>
#include <queue>
#define inf 2000000000
#define nmax 50001
#define pb push_back
#define mkp make_pair
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n;
vector < pair<int,int> > G[nmax];
int dmin[nmax],nr[nmax];
queue <int> Q;
bool negativ;

void Citire()
{
    int i,m,x,y,c;
    fin>>n>>m;
    for(i = 0; i < m; i++)
    {
        fin>>x>>y>>c;
        G[x].pb(mkp(y,c));
    }
}

void Bellman_Ford()
{
    vector< pair<int,int> >::iterator it;
    int i,x;
    for(i=2;i<=n;i++) dmin[i]=inf;
    Q.push(1);
    while(!Q.empty() && !negativ)
    {
        x=Q.front(); Q.pop();
        for(it = G[x].begin(); it != G[x].end(); ++it)
            if(dmin[it->first] > dmin[x] + it->second)
        {
            dmin[it->first] = dmin[x] + it->second;
            nr[it->first]++;
            Q.push(it->first);
            if(nr[it->first]>n) negativ=true;
        }
    }
}

void Afisare()
{
    if(negativ) fout<<"Ciclu negativ!";
    else
    {
        for(int i=2; i<=n; i++)
            if(dmin[i]!=inf) fout<<dmin[i]<<' ';
            else fout<<"0"<<' ';
        fout<<'\n';
    }
}
int main()
{
    Citire();
    Bellman_Ford();
    Afisare();
    return 0;
}