#include <bits/stdc++.h>
#define INF 10000
#define x first
#define y second
#define DMAX 50005
using namespace std;

vector <pair<int, int> > v[DMAX];

int d[DMAX], use[DMAX];
priority_queue <int> q;
int n, m;

void dijkstra(int k)
{
    for(int i=1;i<=n;i++)
        d[i]=INF;
    d[k]=0;

    q.push(k);

    while(!q.empty())
    {
        int x=q.top();
        q.pop();
        for(int i=0;i<v[x].size();++i)
        {
            if( d[ v[x][i].x ] > d[x] + v[x][i].y )
            if(use[v[x][i].x]!=n)
            {
                 d[ v[x][i].x ] = d[x] + v[x][i].y;
                use[v[x][i].x]++;
                q.push( v[x][i].x );
            }
            else{
                cout<<"Ciclu negativ!\n";
                return;
            }
        }
    }
    for(int i=2;i<=n;i++)
        printf("%i ", d[i]);

}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

cin>>n>>m;
int a, b, c;
    for(int i=1;i<=m;i++)
    {
        scanf("%i %i %i", &a, &b, &c);
        v[a].push_back({b, c});
    }

    dijkstra(1);

    return 0;
}