#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int nmax=5e4+5,inf=0x3f3f3f3f;

int n,m,dist[nmax],counter[nmax];
vector<pair<int,int>> adj[nmax];
bitset <nmax> inQueue;
queue <int> Q;

void read()
{
    fin>>n>>m;
    int u,v,c;

    for(int i=0;i<m;i++)
    {
        fin>>u>>v>>c;
        adj[u].emplace_back(v,c);
    }
}

bool BellmanFord()
{
    fill(dist+1,dist+n+1,inf);
    dist[1]=0;
    inQueue[1]=true;
    Q.push(1);
    counter[1]=1;

    while(!Q.empty())
    {
        int u=Q.front(),v,c;
        Q.pop();
        inQueue[u]=false;

        for(auto next: adj[u])
        {
            tie(v,c)=next;

            if(dist[v]>dist[u]+c)
            {
                dist[v]=dist[u]+c;

                if(!inQueue[v])
                {
                    inQueue[v]=true;
                    Q.push(v);

                    counter[v]++;
                    if(counter[v]>=n)
                        return false;
                }
            }
        }
    }
    return true;
}

void print()
{
    if(!BellmanFord())
        fout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout<<dist[i]<<" ";
}

int main()
{
    read();
    print();
    return 0;
}