#include <bits/stdc++.h>

using namespace std;

const int NMAX=50005,inf=INT_MAX;

int n,m;
int d[NMAX],counter[NMAX];
vector<pair<int,int>> graph[NMAX];
bitset<NMAX> inQueue;

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

void read()
{
    int x,y,c;
    fin>>n>>m;
    for(int i=0;i<n;i++)
    {
        fin>>x>>y>>c;
        graph[x].emplace_back(y,c);
    }
}

bool BellmanFord()
{
    fill(d+1,d+n+1,inf);

    d[1]=0;
    counter[1]=1;
    queue<int> q;
    q.push(1);

    while(!q.empty())
    {
        int x=q.front(),y,c;
        q.pop();
        inQueue[x]=false;

        for(auto it: graph[x])
        {
            tie(y,c)=it;

            if(d[x]+c<d[y])
            {
                d[y]=d[x]+c;

                if(!inQueue[y])
                {
                    q.push(y);
                    inQueue[y]=true;
                    counter[y]++;
                    if(counter[y]>=n)
                        return false;
                }
            }
        }
    }

    return true;
}

void shortestPath()
{
    if(!BellmanFord())
        fout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout<< (d[i]==inf ? 0 : d[i])<<" ";
}

int main()
{
    read();
    shortestPath();
    return 0;
}