#include<fstream>
#include<utility>
#include<vector>
#include<queue>
#define NMAX 50005
#define INFINIT 999999999

using namespace std;

FILE* f=freopen("bellmanford.in","r",stdin);
FILE* o=freopen("bellmanford.out","w",stdout);

int n,m;
vector<pair<int,int> > graph[NMAX];
int dist[NMAX],nruse[NMAX];
queue<int> q;
bool hasCicle=false;

void Reading()
{
    int x,y,c;
    scanf("%d%d",&n,&m);

    for(int i=0;i<m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        graph[x].push_back(make_pair(y,c));
    }
}

void BellmanFord()
{
    for(int i=1;i<=n;++i)
        dist[i]=INFINIT;

    int k=0;

    dist[1]=0;
    nruse[1]=1;
    q.push(1);
    while(!q.empty())
    {
        k=q.front();
        q.pop();
        for(int i=0;i<graph[k].size();++i)
        {
            int ind=graph[k][i].first;
            int cost=graph[k][i].second;
            if(dist[ind]>dist[k]+cost)
            {
                dist[ind]=dist[k]+cost;
                q.push(ind);
                nruse[ind]+=1;
                if(nruse[ind]==n)
                {
                    hasCicle=true;
                    return ;
                }
            }
        }
    }
}

int main()
{
    Reading();

    BellmanFord();

    if(hasCicle)
        printf("Ciclu negativ!");
    else
        for(int i=2;i<=n;++i)
            printf("%d ",dist[i]);

    fclose(f);
    fclose(o);

    return 0;
}