#include<fstream>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=50010;
const int INF=1<<30;

int n,m;
int dist[MAXN];
bool uz[MAXN];

struct edge{int dest,cost;};
vector<edge> adj[MAXN];
queue<int> q;

void read()
{
    int x,y,c;
    edge aux;
    ifstream fin("bellmanford.in");
    fin>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        fin>>x>>y>>c;
        aux.cost=c;
        aux.dest=y;
        adj[x].push_back(aux);
    }
}
int bellmanford()
{
	/*INITIALIZARE*/
    int i,k;
    for (i=1; i<=n; ++i)
    {
        if (i==1)
            dist[i]=0;
        else
            dist[i]=INF;
    }
    /*RELAXAREA NODURILOR*/
	q.push(1);	uz[1]=true;
	while (!q.empty())
	{
		for (vector<edge>::iterator it=adj[q.front()].begin(); it!=adj[q.front()].end(); ++it)
		{
			if (dist[q.front()]+(*it).cost<dist[(*it).dest])
			{
				dist[(*it).dest]=dist[q.front()]+(*it).cost;
				if (!uz[(*it).dest])
				{
					q.push((*it).dest);
					uz[(*it).dest]=true;
				}
			}
		}
		uz[q.front()]=false;
		q.pop();
	}
	/*CICLU NEGATIV*/
    for (i=1; i<=n; ++i)
    {
        for (vector<edge>::iterator it=adj[i].begin(); it!=adj[i].end(); ++it)
        {
            if (dist[i]+(*it).cost<dist[(*it).dest])
            {
                return 0;
            }
        }
    }
    return 1;
}
void write()
{
	ofstream fout("bellmanford.out");
    int rez=bellmanford();
    if (!rez)
    {
        fout<<"Ciclu negativ!\n";
    }
    else
    {
        for (int i=2; i<=n; ++i)
            fout<<dist[i]<<' ';
        fout<<'\n';
    }
}
int main()
{
    read();
    write();
    return 0;
}