#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector <pair<int,int> > a[50001];
vector <pair<int,int> >::iterator it;
queue <int> coada;
int n,m,x,y,z,dist[50001],vizitat[50001];
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    while(m)
    {
        scanf("%d %d %d\n",&x,&y,&z);
        a[x].push_back(make_pair(y,z));
        m--;
    }
    for(x=2;x<=n;x++)
        dist[x]=50000001;
    coada.push(1);
    while(!coada.empty())
    {
        x=coada.front();
        vizitat[x]++;
        if(vizitat[x]==n)
        {
            printf("Ciclu negativ!\n");
            return 0;
        }
        for(it=a[x].begin();it!=a[x].end();it++)
            if(dist[x]+it->second<dist[it->first])
            {
                dist[it->first]=dist[x]+it->second;
                coada.push(it->first);
            }
        coada.pop();
    }
    for(x=2;x<=n;x++)
        printf("%d ",dist[x]);
    printf("\n");
    return 0;
}