#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
#define maxn 50001
#define pb push_back
vector <int> vec[maxn];
vector <int> cost[maxn];
vector <int> q;
int d[50001];
bool este[maxn];
int cate[maxn];
int n,m;
int main(){
    ifstream fi("dijkstra.in");
    ofstream g("dijkstra.out");
    fi>>n>>m;
    int i,j;
    for(i=1;i<=m;i++){
        int a,b,c;
        fi>>a>>b>>c;
        vec[a].pb(b);
        cost[a].pb(c);
         
        if(i<=n)
            d[i]=100000;
    }
    d[1]=0;
    q.pb(1);
    este[1]=true;
    int f=0,l=0;
    while(f<=l){
        int nod=q[f];
        for(i=0;i<vec[nod].size();i++){
            if(d[vec[nod][i]]>d[nod]+cost[nod][i]){
                d[vec[nod][i]]=d[nod]+cost[nod][i];
                if(este[vec[nod][i]]==false){
                    q.pb(vec[nod][i]);
                    l++;
                    este[vec[nod][i]]=true;
                    cate[vec[nod][i]]++;
                }
            }
        }
        if(cate[nod]>n){
            g<<"Ciclu negativ!";
            return 0;
        }
        este[nod]=false;
        f++;
    }  
    for(i=2;i<=n;i++){
        if(d[i]==100000)
            g<<"0 ";
        else
            g<<d[i]<<" ";
    }
    return 0;
}