#include<fstream>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

const int NMAX = 50010;
const int inf = 1000000000;
vector < pair <int, int> > g[NMAX];
queue <int> q;
int n,m,x,y,z,i,j,D[NMAX],V[NMAX];

int main()
{
    cin>>n>>m;
    while (m--)
    {
        cin>>x>>y>>z;
        g[x].push_back(make_pair(y,z));
    }
    for (i=2;i<=n;i++) D[i]=inf;
    D[1]=0;
    q.push(1);
    int k=0;
    V[1]=1;
    while (!q.empty())
    {
        int v = q.front(); q.pop();
        for (i=0; i< g[v].size();i++)
        {
            int to=g[v][i].first, len=g[v][i].second;
            if (D[v]+len < D[to])
            {
                ++V[to];
                if (V[to]==n)
                    {
                        cout<<"Ciclu negativ!";
                        return 0;
                    }
                D[to]=D[v]+len;
                q.push(to);
            }
        }
    }
    for (i=2;i<=n;i++) cout<<D[i]<<" ";
    return  0;
}