#include <bits/stdc++.h>
#define DM 50005
#define pii pair<int,int>
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
bitset<DM>used;
int best[DM],it[DM],n,m,a,b,c;
vector<pii> v[DM];
queue<int>q;

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i){
        fin>>a>>b>>c;
        v[a].pb({b,c});
    }
    for(int i=2;i<=n;++i) best[i]=INT_MAX;
    q.push(1);
    while(!q.empty()){
        int i=q.front();
        it[i]++;
        if(it[i]>=n){
            fout<<"Ciclu negativ!";
            exit(0);
        }
        for(int j=0;j<v[i].size();++j)
        if(best[v[i][j].x]>v[i][j].y+best[i]){
            best[v[i][j].x]=v[i][j].y+best[i];
            q.push(v[i][j].x);
        }
        q.pop();
    }
    for(int i=2;i<=n;++i)fout<<best[i]<<" ";
    return 0;
}