#include <cstdio>
#include <vector>
#include <set>
using namespace std;
#define Max 50001
#define Inf 0xffffff

vector<pair<int,int> >v[Max];
set<int>s0,s1;
int n,d[Max];

void bellman()
{
    int ok,x,y;
    for(int i=2;i<=n;i++)d[i]=Inf;
    s0.insert(1);
    for(int k=1;k<=n;k++)
    {
        ok=0;
        while(s0.size()>0)
        {
            x=*s0.begin();
            s0.erase(s0.begin());
            for(int i=0;i<v[x].size();i++)
            {
                y=v[x][i].first;
                if(d[y]>d[x]+v[x][i].second)
                {
                    d[y]=d[x]+v[x][i].second;
                    s1.insert(y);
                    ok=1;
                }
            }
        }
        swap(s0,s1);
    }
    if(s0.size()>0)printf("Ciclu negativ!\n"); else
    for(int i=2;i<=n;i++)printf("%d ",d[i]);
}

int main()
{
    int m,x,y,c;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
        scanf("%d %d",&n,&m);
        while(m--)
        {
            scanf("%d %d %d",&x,&y,&c);
            v[x].push_back(make_pair(y,c));
        }
    bellman();
    return 0;
}