#include<stdio.h>
#include<vector>
#include<queue>
#define inf 0x3f3f3f;
#define max 50001
using namespace std;
struct dij
{
    int nod,cost;
};
vector<dij> a[max];
vector<int> d(max,inf);
queue<int> q;
int i,j,p1,p2,p3,n,m;

int dijkstra(int x)
{
    int i;
    q.push(x);
    d[1]=0;
    while(!q.empty())
    {
        x=q.front();
        for(i=0;i<a[x].size();++i)
            if(d[a[x][i].nod]>d[x]+a[x][i].cost)
                d[a[x][i].nod]=d[x]+a[x][i].cost,q.push(a[x][i].nod);

            else
                if(d[a[x][i].nod]>0&&d[x]<0)
                    return 0;
                q.pop();
    }
    return 1;
}
int main()
{
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d %d" ,&n,&m);
        for (i=1;i<=m;i++)
        {
            scanf("%d%d%d" ,&p1,&p2,&p3);
            a[p1].push_back((dij){p2,p3});
        }
        for(i=1;i<=n;i++)
            d[i]=inf;
        if(!dijkstra(1))
            printf("Ciclu negativ!");
        else
            for (i=2;i<=n;i++)
                if(d[i]==inf)
                    printf("%d\n" 0);
                else
                    printf("%d\n" d[i]);
   return 0;
}