#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;
vector <pair <int,int>> G[50005];
int inq[50005],nr[50005];
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m;
const int INF = 1e8;
void bellman_ford(int start)
{
    vector<int>dist(n+1,INF);
    dist[start]=0;
    queue <int> s;
    s.push(start);
    bool negative_cicle = false;
    while(!s.empty() && !negative_cicle)
    {
        int nod = s.front();
        s.pop();
        for(auto x:G[nod])
        if(dist[x.first]>dist[nod]+x.second)
        {
            dist[x.first]=dist[nod]+x.second;
            if(!inq[x.first])
                {
                    inq[x.first] = 1;
                    nr[x.first]++;
                    s.push(x.first);
                    if(nr[x.first] > n)
                    {
                        negative_cicle = 1;
                        break;
                    }
                }
        }
        inq[nod]=0;
    }
    if(negative_cicle)
        g<<"Ciclu negativ!";
    else
    {
        for(int i=2;i<=n;i++)
            g<<dist[i]<<" ";
    }
}
int main()
{
f>>n>>m;
int a,b,c;
for(int i=0;i<m;i++)
{
    f>>a>>b>>c;
    G[a].push_back(make_pair(b,c));
}
bellman_ford(1);
}