#include <bits/stdc++.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int N=50010,oo=1000010;
int n,m,d[N],cnt[N];

vector<pair<int,int>> v[N];
queue<int> q;
bitset<N> IsInQueue;



int main()
{
    int x,y,c;
    f>>n>>m;
    for(; m; m--)
    {
        cin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    fill(d,d+n,oo);
    d[1]=0;

    q.push(1);
    IsInQueue[1]=1;

    while(q.size())
    {
        x=q.front();
        for(auto it:v[x])
        {
            cnt[x]++;
            if(cnt[x]>n)
            {
            cout<<"Ciclu negativ!";
            return 0;
            }
            tie(y,c)=it;
            if(d[y]>=d[x]+c)
            {

                d[y]=d[x]+c;
                if(!IsInQueue[y])
                {
                    q.push(y);
                    IsInQueue[y]=1;
                }
            }
        }
    q.pop();
    IsInQueue[x]=0;
    }

    for(int i=2;i<=n;i++)
        cout<<d[i]<<" ";

    return 0;
}