#include<fstream>
#include<vector>
#include<queue>
#define NMAX 50010
#define MMAX 250010
#define INF 250000000
 
using namespace std;
 
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
 
struct muchie
{
    int x, cost, ord;
} t;
 
int n, m, nr[MMAX], vz[NMAX], cmin[NMAX];
int i, changes, nod, val;
vector<muchie> v[NMAX];
queue<int> q;

 
int main()
{
	int x, y, cost, i;
    
    f >> n >> m;
	
    for (i=1; i<=m; i++)
    {
        f >> x >> y >> cost;
        t.cost=cost;
        t.ord=i;
        t.x=y;
        v[x].push_back(t);
    }
	
    for (i=1; i<=n; i++)
        cmin[i]=INF;
	
	
    q.push(1);
    cmin[1]=0;
    while (!changes && !q.empty())
    {
        nod=q.front();
        q.pop();
        for (i=0; i<int(v[nod].size()); i++)
        {
            t=v[nod][i];
            val=cmin[nod]+t.cost;
            if (val<cmin[t.x])
            {
                cmin[t.x]=val;
                q.push(t.x);
                nr[t.ord]++;
                if (nr[t.ord]==n)
                {
                    changes=1;
                    break;
                }
            }
        }
    }
    if (changes)
        g << "Ciclu negativ!";
    else
        for (i=2; i<=n; i++)
            g << cmin[i] << " ";
		
    f.close();
    g.close();
    return 0;
}