#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream ff("bellmanford.in");
ofstream gg("bellmanford.out");
 
#define max 50001
#define inf 0xffffff
struct per{ int b,c; per(int b0=0,int c0=0){b=b0; c=c0;}};
vector<per> vv[max];
int ww[max], qq[2][max], q[2];
int n, m, dd[max];
 
void bel(){
    int x0=0, x1=1, x, y, c, l;
    for(int i=1;i<=n;i++) dd[i]=inf;
    dd[1]=0;
    qq[x0][q[x0]++]=1;
    for(int k=1;k<=n;k++){
        while(q[x0]>0){
            x=qq[x0][--q[x0]];
            l=vv[x].size();
            for(int i=0;i<l;i++){
                y=vv[x][i].b;
                c=vv[x][i].c;
                if(dd[y]>dd[x]+c){
                    dd[y]=dd[x]+c;
                    if(ww[y]!=k){qq[x1][q[x1]++]=y; ww[y]=k;}
                }
            }
        }
        x0^=1; x1^=1;
    }
    if(q[x0]>0)  gg << "Ciclu negativ!"; else
    for(int i=2;i<=n;i++) gg << dd[i] << " ";
}
 
int main(){
    int a, b, c;
    ff >> n >> m;
    for(int i=0;i<m;i++){
        ff >> a >> b >> c;
        vv[a].push_back(per(b,c));
    }
    bel();
    return 0;
}