#include <fstream>
#include <queue>
#include <bitset>
#define MAX 50003
#define INFINITE 50000003

using namespace std;

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

vector <pair <int,int> > la[MAX];
queue <int> q;

int n,m,d[MAX],nrelax[MAX];

bitset <MAX> incoada;

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        fin>>u>>v>>w;
        la[u].push_back(make_pair(v,w));
    }
}

int bellman()
{
    int u,v,w;
    for(int i=2;i<=n;i++)
        d[i]=INFINITE;
    q.push(1);
    incoada[1]=1;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        incoada[u]=0;
        nrelax[u]++;
        if(nrelax[u]==n)
            return 0;
        for(int i=0;i<la[u].size();i++)
        {
            v=la[u][i].first;
            w=la[u][i].second;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                if(!incoada[v])
                {
                    q.push(v);
                    incoada[v]=1;
                }

            }
        }
    }
    return 1;
}
int main()
{
    citire();
    int rez=bellman();
    if(!rez)
        fout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout<<d[i]<<' ';
    return 0;
}