#include <iostream>
#include<vector>
#include<fstream>
#include<queue>
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int MAX_N = 50005;
const int INF = 0x3f3f3f3f;

int n,m;
bool negativ=false;

vector<int>d(MAX_N,INF); // vector de distante
vector<int>cnt_in_queue(MAX_N,0); //
vector<pair<int,int> >L[MAX_N];
queue<int>Q;
vector<bool>viz(MAX_N,false);
void citire()
{
    int x,y,c,i,j;
    fin>>n>>m;

    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
}

void bellman(int st)
{
    Q.push(st);
    d[st]=0;
    viz[st]=true;

    while(!Q.empty() && negativ == false)
    {
        int x=Q.front();
        Q.pop();
        viz[x]=false;

        for(auto e:L[x])
            if(d[x] < INF)
        {
            if(d[e.first] > d[x] + e.second)
            {
                d[e.first] = d[x] + e.second; /// facem update
                if(!viz[e.first])
                {
                    if(cnt_in_queue[e.first] > n)
                        negativ=true;
                    else
                    {
                        Q.push(e.first);
                        viz[e.first]=true;
                        cnt_in_queue[e.first]++;
                    }
                }
            }
        }

    }
}

int main()
{
    citire();
    bellman(1);
    if(negativ)
        fout<<"Ciclu negativ!\n";
    else for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";
    return 0;
}