#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int maxx=50005;
const int pinf=1<<29;
typedef pair<int,int> per;

int n, m, d[maxx], fv[maxx], ok;
vector<per> g[maxx];

void citire(vector <per> g[], int &n, int &m)
{
    int x, y, c, i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }
}

void BF(vector<per> g[], int n, int d[], int fv[])
{
    bool v[maxx];
    int i, j, z;
    queue<int> q;
    vector<per> :: iterator it;

    for(i=1; i<=n; i++)
    {
        d[i]=pinf;
        v[i]=false;
    }

    d[1]=0;
    v[1]=true;
    q.push(1);

    while(!q.empty())
    {
        z=q.front();

        for(it=g[z].begin(); it!=g[z].end(); it++)
        {
            if(d[z]+it->second < d[it->first])
            {
                d[it->first]=d[z]+it->second;
                q.push(it->first);

                fv[it->first]++;
                if(fv[i]>n-1)
                {
                    fout<<"Ciclu negativ!";
                    ok=1;
                    exit(0);
                }
            }
        }

        q.pop();
    }
}

void afisare(int n)
{
    int i;

    for(i=2; i<=n; i++)
        fout<<d[i]<<" ";
}

int main()
{
    citire(g,n,m);
    BF(g,n,d,fv);

    if(ok==0)
        afisare(n);
    return 0;
}