#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;


vector <pair <int,int> > dr[50005];
std::queue<int> q;
int n,m,len[50005],ok[50005];
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");


int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        dr[x].push_back({y,z});
    }
    q.push(1);
    for(int i=2; i<=n; i++)
        len[i]=INT_MAX;
    int i;
    for(i=1; i<=n+1&&!q.empty(); i++)
    {
        int vr=q.size();
        for(int pk=1;pk<=vr;pk++)
        {int k=q.front();
        q.pop();
        ok[k]=0;
        for(auto &v:dr[k])
        {
            int x,y;
            x=v.first;
            y=v.second;
            if(len[x]>len[k]+y)
            {
                len[x]=len[k]+y;
                if(!ok[x])
                {
                    ok[x]++;
                    q.push(x);
                }
            }

        }
        }

    }
    if(i==n+2)
        g<<"Ciclu negativ!";
    else
        for(int i=2; i<=n; i++)
            g<<len[i]<<' ';



    return 0;
}