#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

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

const int N = 5e4;
const int INF = 2e9;
const int START = 1;

int n, m;
int cont[N + 5];
vector<int> d(N + 5, INF);
vector<pair<int, int>> adj[N + 5];
bitset<N + 5> inQueue;

bool bellmanFord()
{
    queue<int> q;
    q.push(START);
    d[START] = 0;
    cont[START] = inQueue[START] = 1;

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

        for(auto it: adj[node])
        {
            if(d[node] + it.second < d[it.first])
            {
                d[it.first] = d[node] + it.second;
                if(!inQueue[it.first])
                {
                    q.push(it.first);
                    inQueue[it.first] = 1;
                    cont[it.first]++;

                    if(cont[it.first] == n)
                        return 0;
                }
            }
        }
    }

    return 1;
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;

        adj[x].emplace_back(y, c);
    }

    if(!bellmanFord())
        out << "Ciclu negativ!\n";
    else
    {
        for(int i = 2; i <= n; i++)
            out << d[i] << ' ';
        out << '\n';
    }

    return 0;
}