#include <fstream>
#include <vector>
#include <queue>
#define inf 1000000007
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
vector <pair<int,pair<int,int> > >v;
vector <pair<int,int > >pq;
pair<int,int>t;
int n,m,a,b,c,d[50010];
int main()
{
    fin>>n>>m;
    for(;m;m--)
    {
        fin>>a>>b>>c;
        v.push_back(make_pair(c,make_pair(a,b)));
        ///v.push_back(make_pair(c,make_pair(b,a)));
        if(b==1)
            pq.push_back(make_pair(c,a));
    }
    for(int i=2;i<=n;i++) d[i]=inf;
    d[1]=0;

    for(int i=1;i<n;i++)
    {
        for(auto it:v)
        {
            if(d[it.second.first]+it.first<d[it.second.second])
                d[it.second.second]=d[it.second.first]+it.first;
        }
    }
    bool ok=1;
    for(auto it:pq)
    {
        if(d[it.second]+it.first<0)
        {
            ok=1;
            fout<<"Ciclu negativ!";
            break;
        }
    }
    if(ok)
    {
        for(int i=2;i<=n;i++)
            fout<<d[i]<<" ";
    }

    return 0;
}