#include <cstdio>
#include <vector>
#include <set>
using namespace std;
#define MAX 50001
#define inf 0xfffffff

vector<pair<int,int> >g[MAX];
set<int>s1,s2;

int n,dist[MAX];

void bellman(){
    bool ok;
    int x,y;
    for(int i=2;i<=n;i++) dist[i] = inf;
    s1.insert(1);
    for(int p=1;p<=n;p++)
    {
        ok = 0;
        while( s1.size()>0 )
        {
            x = *s1.begin(); s1.erase(s1.begin());
            for(int i=0;i<g[x].size();i++)
            {
                y = g[x][i].first;
                if( dist[y] > dist[x] + g[x][i].second )
                {
                    dist[y] = dist[x] + g[x][i].second;
                    s2.insert(y);
                    ok = 1;
                }
            }
        }
        swap(s1,s2);
    }
    if(ok)printf("Ciclu negativ!\n"); else
    for(int i=2;i<=n;i++)printf("%d ",dist[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);
            g[x].push_back(make_pair(y,c));
        }
        bellman();
        return 0;
}