#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

void bellman(vector<vector<pair<int,int>>> &noduri,vector<int> &v)
{
    queue<pair<int,int>> q;
    q.push({1,0});
    vector<int> visited(noduri.size(),0),cicluri;
    while (q.size()!=0)
    {
        pair<int,int> aux = q.front();
        q.pop();
        for (int j = 0; j < noduri[aux.first].size(); j++)
        {
            if (aux.second + noduri[aux.first][j].second < v[noduri[aux.first][j].first])
            {
                v[noduri[aux.first][j].first] = aux.second + noduri[aux.first][j].second;
                visited[noduri[aux.first][j].first]++;
                if (visited[noduri[aux.first][j].first]!=noduri.size())
                {
                    q.push({noduri[aux.first][j].first ,aux.second + noduri[aux.first][j].second});
                }
                else
                {
                    v[0] = -1;
                    return;
                }
            }
        }
    }
}

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
    int n,m;    
    in >> n >> m;

    vector<vector<pair<int,int>>> noduri(n+1);
    for (int i = 0; i < m; i++)
    {
        int x,y,z;
        in >> x >> y >> z;
        noduri[x].push_back({y,z});
    }
    vector<int> v(n+1,999999);
    bellman(noduri,v);
    if (v[0] == -1)
    {
        out << "Ciclu negativ!";
    }
    else
    {
        for (int i = 2; i <= n; i++)
        {
            out << v[i] << " ";
        }
        
    }
    
    

    return 0;
}