#include <fstream>

#include <vector>

#include <set>



using namespace std;



ifstream fin("bellmanford.in");

ofstream fout("bellmanford.out");



const int N=50000+5;

const int M=250000+5;



struct road

{

        int a;

        int b;

        int c;

};



int n,m,d[N];

vector<int>v[N];

road e[M];



int main()

{

        fin>>n>>m;

        for(int i=1;i<=n;i++)

        {

                fin>>e[i].a>>e[i].b>>e[i].c;

                v[e[i].a].push_back(i);

        }

        d[1]=0;

        for(int i=2;i<=n;i++)

        {

                d[i]=(1<<30);

        }

        set<pair<int,int>>s;

        s.insert({0,1});

        for(long long itr=1;itr<=n*(long long)m && !s.empty();itr++)

        {

                int nod=s.begin()->second;

                s.erase(s.begin());

                for(auto it:v[nod])

                {

                        if(d[nod]+e[it].c<d[e[it].b])

                        {

                                d[e[it].b]=d[nod]+e[it].c;

                                s.insert({d[e[it].b],e[it].b});

                        }

                }

        }

        for(int i=1;i<=m;i++)

        {

                if(d[e[i].a]+e[i].c<d[e[i].b])

                {

                        fout<<"Ciclu negativ!\n";

                        return 0;

                }

        }

        for(int i=2;i<=n;i++)

        {

                fout<<d[i]<<" ";

        }

        fout<<"\n";

        return 0;

}