#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#define pb push_back
#define mp make_pair
#define INF 99999999
using namespace std;
int N, M, Ciclu, D[50100], Waiting[50100], Uses[50100];
queue<int> Q;
vector<pair<int, int> > G[50100];
void Load_Data()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for (int i=1; i<=M; i++)
    {
        int x, y, cost;
        scanf("%d%d%d", &x, &y, &cost);
        G[x].pb( mp(cost, y) );
    }
}
void Initialize()
{
    for (int i=2; i<=N; i++) D[i]=INF;
    D[1]=0;
    memset(Waiting, 0, sizeof(Waiting) );
    Waiting[1]=1;
    Q.push( 1 );
    Ciclu=0;
}
void Solve()
{
    while (!Q.empty() )
    {
        int Nod=Q.front();
        Q.pop();
        for (vector<pair<int, int> >::iterator it=G[Nod].begin(); it!=G[Nod].end(); it++)
            if (D[Nod]+(*it).first<D[(*it).second])
            {
                Uses[(*it).second]++;
                if (Uses[(*it).second]>=N) {Ciclu=1;printf("Ciclu negativ!\n");break;}
                D[(*it).second]=D[Nod]+(*it).first;
                if (!Waiting[(*it).second]) Q.push((*it).second),Waiting[(*it).second]=1;
            }
        Waiting[Nod]=0;
    }
}
int main()
{
    Load_Data();
    Initialize();
    Solve();
    if (!Ciclu) for (int i=2; i<=N; i++) printf("%d ",D[i]);
    return 0;
}