#include <bits/stdc++.h>
#define vec it.first
#define cst it.second
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int N = 50010;
const int oo = 1000000000;
vector<pair<int,int>> v[N];
queue<int> Q;
bitset<N> q;
int n,m,x,y,c,d[N],cnt[N];
int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    for(int i=2;i<=n;i++)
        d[i]=oo;
    Q.push(1);
    q[1]=1;
    while(Q.size())
    {
        x=Q.front();Q.pop();q[x]=0;
        for(auto it:v[x])
        {
            /// vecin = vec
            /// cost_muchie = cst
            if(d[vec]>d[x]+cst)
            {
                d[vec]=d[x]+cst;
                if(!q[vec])
                {
                    cnt[vec]++;
                    if(cnt[vec]==n)
                    {
                        g<<"Ciclu negativ!";return 0;
                    }
                    Q.push(vec);
                    q[vec]=1;
                }
            }
        }
    }
    for(int i=2;i<=n;i++)
        g<<d[i]<<' ';
    return 0;
}