#include <bits/stdc++.h>
#define NMAX 50010
#define INF INT_MAX
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector< pair<int, int> > G[NMAX];
int n,m;
void citire(){
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int from, to, cost;
        f>>from>>to>>cost;
        G[from].push_back(make_pair(to, cost));
    }
}
queue <int> q;
vector <int> cost(NMAX, INF);
int inq[NMAX];
bitset <NMAX> b(false);
void bellman(){
    q.push(1);
    b[1]=true;
    cost[1]=0;
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        b[nod]=false;
        if(cost[nod]==INF)continue;
        for(auto it:G[nod]){
            int newnode = it.first;
            int newcost = it.second;
            if(cost[newnode]>cost[nod]+newcost){
                cost[newnode] = cost[nod] + newcost;
                if(b[newnode])continue;
                if(inq[newnode]>n)
                   {
                       g<<"Ciclu negativ!\n";
                       return;
                   }
                inq[newnode]++;
                q.push(newnode);
                b[newnode] = true;
            }
        }
    }
    for(int i=2;i<=n;i++)g<<cost[i]<<" ";
}
int main()
{
    citire();
    bellman();
    return 0;
}