#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;

#define NMAX 50005
struct nod
{
    int c,y;
};

struct cmp
{
    bool operator()(const nod a,const nod b)
    {
       return a.c > b.c;
    }
};

vector <nod> g[NMAX];
vector <int> v;
priority_queue <nod, vector<nod> , cmp> q;
int d[NMAX];

int functie(int m, int n)
{
    nod x;
    int i=1;
    x.y=m;
    x.c=0;
    q.push(x);
    int s;

    while(!(q.empty()))
   {
        s=q.top().y;
        if(s==1)
            i++;
        if(i==n)return 0;
        q.pop();
        for(int j=0; j<g[s].size(); j++)
        {
            if(d[g[s][j].y]>d[s]+g[s][j].c)
           {
               x.y=g[s][j].y;
               x.c=d[s]+g[s][j].c;
               q.push(x);
               d[g[s][j].y]=d[s]+g[s][j].c;
           }
        }
   }
   return 1;
}

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

    int n, m, a, b, c;
    nod x;
    scanf("%d %d \n", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %d \n", &a,&b,&c);
        x.y=b;
        x.c=c;
        g[a].push_back(x);
    }

    for(int i=2; i<=n; i++) d[i]=NMAX*100;
    if(functie(1,n)==0)
        cout<<"Ciclu negativ!";
    else
    {
        for(int i=2; i<=n; i++)
            cout<<d[i]<<" ";
    }




    return 0;
}