#include <cstdio>
#include <vector>
#include <queue>
#define pb push_back
#define mp make_pair
#define y first
#define cost second
using namespace std;
const int N=50100;
const int INF = 0x3f3f3f3f;
vector <pair<int,int> > much[N];
vector <int> dist(N,INF),apar(N,0);
int n,m;
void citire()
{
    freopen("bellmanford.in","r",stdin);
    scanf("%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        much[a].pb(mp(b,c));
    }
    fclose(stdin);
}
void bellmanFord()
{
    queue <int> coada;
    bool inCoada[N]={0};
    coada.push(1);
    dist[1]=0;
    apar[1]++;
    while(!coada.empty())
    {
        int nc=coada.front(),nv;
        coada.pop();
        inCoada[nc]=0;
        for(int i=0;i<much[nc].size();++i)
        {
            nv=much[nc][i].y;
            if(dist[nv]>dist[nc]+much[nc][i].cost)
            {
                dist[nv]=dist[nc]+much[nc][i].cost;
                if(inCoada[nv]>n){
                    printf("Ciclu Negativ!\n");
                    return;
                }
                coada.push(nv);
                apar[nv]++;
                inCoada[nv]=1;
            }
        }
    }
    for(int i=2;i<=n;++i)
        if(dist[i]<INF)
        printf("%d ",dist[i]);
        else printf("0 ");
    printf("\n");
}
int main()
{
    freopen("bellmanford.out","w",stdout);
    citire();
    bellmanFord();
    return 0;
}