#include <fstream>
#include <vector>
#include <queue>
#define in "bellmanford.in"
#define out "bellmanford.out"
#define N 50003
#define oo 1e7

using namespace std;

ifstream fin(in);
ofstream fout(out);

int n,m,x,y,c;
int viz[N],d[N];

queue<int> q;
vector<pair<int,int> >g[N];

void citire()
{
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }
}

bool BF()
{
    for(int i=2; i<=n; ++i)
        d[i] = oo;

    int nod;
    int k,p;

    q.push(1);
    while(!q.empty())
    {
        nod = q.front();
        ++viz[nod];

        if(viz[nod] >= n) return 0;

        q.pop();

        for(int i=0; i<g[nod].size(); ++i)
        {
            k = g[nod][i].first; // nodurm
            p = g[nod][i].second; //cost

            if(d[k] > d[nod] + p)
            {
                d[k] = d[nod] + p;
                q.push(k);
            }
        }
    }
    return 1;
}

int main()
{
    citire();

    if(!BF()) fout<<"Ciclu negativ!";
        else
            for(int i=2; i<=n; ++i)
                fout<<d[i]<<" ";


    fin.close(); fout.close();
    return 0;
}