#include <bits/stdc++.h>
#define oo 1<<30

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int NMAX = 50001;
vector<pair<int,int> > muchii[NMAX];
int n,m;
int best[NMAX];
queue<int> coada;
int dist[NMAX];

void citire()
{
    in>>n>>m;
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        muchii[x].push_back(make_pair(y,z));
    }
    in.close();
}

int bellman()
{
    for(int i=2;i<=n;i++)
        best[i]=oo;
    int target,cost;
    int ok = 1;
    coada.push(1);
    while(!coada.empty() && ok)
    {
            int j = coada.front();
            for(unsigned int k=0;k<muchii[j].size();k++)
            {
                target = muchii[j][k].first;
                cost  = muchii[j][k].second;
                if(best[target] > best[j] + cost)
                {
                    best[target] = best[j] + cost;
                    coada.push(target);
                    dist[target] = dist[j] + 1;
                    if(dist[target] > n-1)
                        ok = 0;
                }
                if(!ok) break;
            }
        coada.pop();
    }
    return ok;
}

int main()
{
    citire();
    if(bellman())
    {
        for(int i=2;i<=n;i++)
            out<<best[i]<<" ";
    }
    else
        out<<"Ciclu negativ!";
    out.close();
    return 0;
}