#include <iostream>
#include <fstream>
#include <queue>
#include <map>
#include <vector>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct node{
    int num;
    int cost;
};

vector< vector<node> > con;
vector<bool> inque;
int n, m;
vector<int> minn;
bool no1=true;

void cfind(){
    queue<int> q;
    q.push(1);
    inque[1]=true;
    while(!q.empty() && no1){
        int cn=q.front();
        vector<node> cc=con[cn];
        for(int i=0;i<cc.size() && no1;i++){
            int nn=cc[i].num;
            int c=cc[i].cost;
            if(minn[cn]+c<minn[nn]){
                minn[nn]=minn[cn]+c;
                if(!inque[nn]){
                    if(nn==1) no1=false;
                    q.push(nn);
                    inque[nn]=true;
                }
            }
        }
        q.pop();
        inque[cn]=false;
    }
}

int main()
{
    fin>>n>>m;
    minn.assign(n+1, 1000000);
    minn[1]=0;
    node temp;
    con.assign(m+1, vector<node>(0, temp));
    inque.assign(n+1, false);
    int x;
    for(int i=1;i<=m;i++){
        fin>>x;
        fin>>temp.num;
        fin>>temp.cost;
        con[x].push_back(temp);
    }
    cfind();
    if(minn[1]<0) fout<<"Ciclu negativ!";
    else for(int i=2;i<minn.size();i++) fout<<minn[i]<<' ';
    return 0;
}