#include <iostream>
#include <limits.h>
#include <cmath>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <map>
#include <fstream>
#include <list>
#include <queue>
#include <iomanip>
#include <deque>
#include <set>

using namespace std;

#define mm 50001
#define inf (1<<30)
#define pb push_back
#define mp make_pair

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define cin f
#define cout g

int dist[50001],prec[50001];
vector<int> v[50001],w[50001];
queue<int> q;
int neg[50001];

void Init(int n)
{
    dist[1] = 0;
    neg[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        dist[i] = inf;
        neg[i] = 0;
    }
}

int BellmanFord(int n)
{
    q.push(1);
    while(!q.empty())
    {
        int node = q.front();
        q.pop();

            if(neg[node] >= n)
                return 0;

            for(int i = 0; i < v[node].size(); i++)
                if(w[node][i] + dist[node] < dist[v[node][i]])
            {
                dist[v[node][i]] = w[node][i] + dist[node];
                q.push(v[node][i]);
                neg[v[node][i]]++;
            }

    }

    return 1;
}


int main()
{
    int n,m;
    cin>>n>>m;

    for(int i = 1; i <= m; i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        v[x].pb(y);
        w[x].pb(z);
    }

    Init(n);
    if(BellmanFord(n))
        for(int i = 2; i <= n; i++)
            cout<<dist[i]<<" ";
    else
        cout<<"Ciclu negativ!";

 return 0;
}