#include<cstdio>
#include<vector>
using namespace std;
const int MAXN=50010;
const int INF=1<<30;
int n,m;
int dist[MAXN],pred[MAXN];
struct edge{int dest,cost;};
vector<edge> adj[MAXN];
void read()
{
    int x,y,c;
    edge aux;
    freopen("bellmanford.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; ++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        aux.cost=c;
        aux.dest=y;
        adj[x].push_back(aux);
    }
}
int bellmanford()
{
    int i,k;
    for (i=1; i<=n; ++i)
    {
        if (i==1)
            dist[i]=0;
        else
            dist[i]=INF;
        pred[i]=0;
    }
	for (k=1; k<=n; ++k)
	{
		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])
				{
					dist[(*it).dest]=dist[i]+(*it).cost;
					pred[(*it).dest]=i;
				}
			}
		}
	}
    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()
{
    freopen("bellmanford.out","w",stdout);
    int rez=bellmanford();
    if (!rez)
    {
        printf("Ciclu negativ!\n");
    }
    else
    {
        for (int i=2; i<=n; ++i)
            printf("%d ",dist[i]);
        printf("\n");
    }
}
int main()
{
    read();
    write();
    return 0;
}