#include <fstream>
#include <vector>
#include <bitset>
#include <deque>

#define DIM 50002

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,i,a,b,c,d[DIM],nod,nou,cost,nr[DIM];
vector < pair<int, int> > G[DIM];
bitset <DIM> viz;
deque <int> q;
int bellu(int x)
{
    q.push_back(x);
    d[x]=0;
    while(!q.empty())
    {
        nod=*q.begin();
        for(i=0;i<G[nod].size();i++)
        {
            nou=G[nod][i].first;
            cost=G[nod][i].second;
            if(d[nou]>d[nod]+cost)
            {
                d[nou]=d[nod]+cost;
                if(viz[nou]==0)
                {
                    viz[nou]=1;
                    q.push_back(nou);
                    nr[nou]++;
                    if(nr[nou]==n)
                    {
                        return 0;
                    }
                }
            }
        }
        q.pop_front();
        viz[nod]=0;
    }
    return 1;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }
    for(i=1;i<=n;i++)
        d[i]=1000*250000;
    if(bellu(1)==0)
        fout<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
            fout<<d[i]<<' ';
    return 0;
}