#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

int d[50005], ex[50005], frec[50005];
vector <pair<int, int>> graph[50005];
deque <int> q;

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int n, m, x, y, z;
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        graph[x].push_back(make_pair(y,z));
    }
    for(int i=2; i<=n; i++)
        d[i] = 10001;
    d[1] = 0;
    q.push_back(1);
    while(!q.empty())
    {
        int k = q.front();
        frec[k]++;
        if(frec[k]>n)
        {
            g<<"Ciclu negativ!";
            return 0;
        }
        q.pop_front();
        ex[k] = 0;
        for(auto j : graph[k])
        {
            if(d[k] + j.second < d[j.first])
            {
                d[j.first] = d[k] + j.second;
                if(ex[j.first] == 0)
                {
                    ex[j.first] = 1;
                    q.push_back(j.first);
                }
            }
        }
    }
    for(int i=2; i<=n; i++)
        g<<d[i]<<" ";
    return 0;
}