#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream go("bellmanford.out");
struct edge{
int next,c;};
vector <edge> g[50000];
queue <int> q;
vector <edge> ::iterator it;
int best[50000],in[50000],n,m;
int inf=1001;
int main()
{
    f>>n>>m;
    edge p;
    int x,y,cost;
    for(int i=1;i<=m;i++){
            f>>x>>y>>cost;
            p.next=y;
            p.c=cost;
            g[x].push_back(p);
            p.next=x;
            g[y].push_back(p);
    }
    for(int i=1;i<=n;i++)
        best[i]=inf;
    best[1]=0;
    q.push(1);
    int flag=1;
    while(!q.empty()){
            int node=q.front();
            in[node]++;
            q.pop();
            for(auto &it: g[node]){
                    if(best[it.next]==inf){
                            if(best[it.next]>=best[node]+it.c){
                            best[it.next]=best[node]+it.c;
                            /*if(in[it.next])*/ q.push(it.next);}
                    }
            if(in[node]>n+10) flag=0;
            }
    }
    if(flag==0) go<<"Ciclu negativ!";
    else for(int i=2;i<=n;i++) go<<best[i]<<' ';
    return 0;
}