#include<cstdio>
#include<vector>
//#inc
using namespace std;
const int MAXN=50010;
const int INF=1<<30;
int n,m,inc,sf=-1;
int dist[MAXN],q[MAXN*50];
bool uz[MAXN];
struct edge{int dest,cost;};
vector<edge> adj[MAXN];
void push(int x)
{
	uz[x]=true;
	q[++sf]=x;
}
void pop()
{
	uz[q[inc]]=false;
	q[inc++]=0;
}
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;
    }
		push(1);
		while (inc<=sf)
		{
			for (vector<edge>::iterator it=adj[q[inc]].begin(); it!=adj[q[inc]].end(); ++it)
			{
				if (dist[q[inc]]+(*it).cost<dist[(*it).dest])
				{
					dist[(*it).dest]=dist[q[inc]]+(*it).cost;
					if (!uz[(*it).dest])
						push((*it).dest);
				}
			}
			pop();
		}
    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");
    }
    printf("%d",sizeof(q)/1024/1024);
}
int main()
{
    read();
    write();
    return 0;
}