#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[N];

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;
}