#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;struct qer{int dir,cost;}nxt;
ifstream fin("bellmanford.in");ofstream fout("bellmanford.out");
vector<qer>v[50001];
int n,m,dist[50001],cnt[50001],a,b,c,idx,i;bool inside[50001];
const int INF=1e9;
queue<int>q;
int main()
{
    fin>>n>>m;
    for(i=2;i<=n;i++)dist[i]=INF;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        v[a].push_back({b,c});
    }q.push(1);
    while(!q.empty()){
        idx=q.front();
        inside[idx]=0;
        q.pop();
        for(i=0;i<v[idx].size();i++){
            nxt=v[idx][i];
            if(dist[idx]+nxt.cost<dist[nxt.dir]){
                dist[nxt.dir]=dist[idx]+nxt.cost;
                if(!inside[nxt.dir]){
                    q.push(nxt.dir);
                    inside[nxt.dir]=1;
                    cnt[nxt.dir]=cnt[idx]+1;
                    if(cnt[nxt.dir]>n){
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for(i=2;i<=n;i++)fout<<dist[i]<<' ';
    return 0;
}