//#include <bits/stdc++.h>
//
//using namespace std;
//
//#define pb push_back
//#define INF 1000000000
//
//struct edge
//{
//    int a, b, c;
//};
//int n, m;
//vector <edge> edges;
//vector <int> d;
//
//int main()
//{
//    ios_base :: sync_with_stdio(0);
//    cin.tie(0);
//
//    freopen("bellmanford.in", "r", stdin);
//    freopen("bellmanford.out", "w", stdout);
//
//    cin >> n >> m;
//    for(int i = 1; i <= m; i ++)
//    {
//        int x, y, c;
//        cin >> x >> y >> c;
//        edges.pb({x, y, c});
//    }
//
//    d.resize(n + 1, INF);
//
//    d[1] = 0;
//    bool any;
//    for(int i = 0; i < n; i ++)
//    {
//        any = 0;
//        for(edge x : edges)
//        {
//            if(d[x.a] < INF)
//            {
//                if(d[x.b] > d[x.a] + x.c)
//                {
//                    d[x.b] = d[x.a] + x.c;
//                    any = 1;
//                }
//            }
//        }
//    }
//
//    if(any)
//        cout << "Ciclu negativ!";
//    else
//        for(int i = 2; i <= n; i ++)
//            cout << d[i] << " ";
//    return 0;
//}

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define INF 1000000000
#define MAX_N 50000

struct edge
{
    int a, b, c;
};

int n, m;
vector <vector <pair <int, int> > > graph;
vector <int> d, timesInserted, parent;
bitset <MAX_N + 1> inQueue;
queue <int> q;


void bellmanFord(int start)
{
    bool hasNegativeCycle = 0;
    d[start] = 0;
    q.push(start);
    inQueue[start] = 1;
    timesInserted[start] ++;
//    parent.resize(n + 1);

    while(!q.empty()  &&  timesInserted[q.front()] <= n)
    {
        int node = q.front();
        q.pop();
        inQueue[node] = 0;

        for(pair <int, int> x : graph[node])
        {
            if(d[x.first] > d[node] + x.second)
            {
                d[x.first] = d[node] + x.second;
                if(!inQueue[x.first])
                {
                    q.push(x.first);
//                    parent[x.first] = node;
                    timesInserted[x.first] ++;
                    inQueue[x.first] = 1;
//                    if(timesInserted[x.first] > n)/// > sau >=
//                    {
//                        cout << "Ciclu negativ!";
//                        return ;
//                    }
                }
            }
        }
    }
    if(!q.empty())
    {
        cout << "Ciclu negativ!";
        return ;
    }

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

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    cin >> n >> m;
    graph.resize(n + 1);
    for(int i = 1; i <= m; i ++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        graph[x].pb({y, c});
    }

    d.resize(n + 1, INF);
    timesInserted.resize(n + 1);

    bellmanFord(1);
    return 0;
}