/*#include<fstream>
#include<vector>
#define N 50001
using namespace std;
ifstream F("bellmanford.in");
ofstream G("bellmanford.out");
vector<int> g[N],h[N];
int m,n,i,k,l,r,d[N],e[7*N],u[N],j,t;
bool v[N];
int main()
{
    F>>n>>m;
    while(m--)
        F>>i>>j>>k,g[i].push_back(j),h[i].push_back(k);
    for(i=1;i<=n;++i)
        d[i]=N;
    for(k=l=r=d[1]=0,e[r++]=v[1]=1;l<r&&!k;)
        for(i=e[l++],t=g[i].size(),v[i]=0,j=0;j<t&&!k;++j)
            if(d[g[i][j]]>d[i]+h[i][j]) {
                d[g[i][j]]=d[i]+h[i][j];
                if(!v[g[i][j]]) {
                    if(u[g[i][j]]>n)
                        k=1;
                    else
                        e[r++]=g[i][j],v[g[i][j]]=1,++u[g[i][j]];
                }
            }
    if(k)
        G<<"Ciclu negativ!";
    else
        for(i=2;i<=n;++i)
            G<<d[i]<<" ";
    return 0;
}*/
#include <bits/stdc++.h>
#define maxm 250100
#define maxn 50100
#define pii pair<int,int>
#define cl first
#define pr second
using namespace std; int N,M,C[maxn],B[maxn]; queue<int> Q; vector<pii> V[maxn]; int main(){ ifstream cin("bellmanford.in"); ofstream cout("bellmanford.out"); cin >> N >> M; for(int x,y,c;M--;){ cin >> x >> y >> c; V[x].push_back({y,c}); } for(int i = 2;i<=N;i++) C[i]=(1<<30); Q.push(1);while(!Q.empty()){int x = Q.front(); Q.pop();B[x]++;if(B[x] >= N) return cout << "Ciclu negativ!",0;for(auto y:V[x]) if(C[y.cl] > C[x] + y.pr) C[y.cl] = C[x] + y.pr, Q.push(y.cl);}for(int i = 2;i<=N;i++) cout << C[i] << ' ';}