#include<fstream>
#include<vector>
#include<queue>

using namespace std;

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


const int Nmax=50000,oo=2000000000;
vector <pair <int, int> > G[Nmax+5];
queue <int> Q;
int N,M,Use[Nmax+5],DP[Nmax+5];
bool InQ[Nmax+5];

void Bellman_Ford(){
    Q.push(1);
    DP[1]=0;
    InQ[1]=1;
    while(!Q.empty()){
        int X=Q.front();
        InQ[X]=0;
        Q.pop();
        Use[X]++;
        if(Use[X]>N){
            fout<<"Ciclu negativ!\n";
            return;
        }
        for(auto i : G[X])
            if(DP[i.first]>DP[X]+i.second){
                DP[i.first]=DP[X]+i.second;
                if(InQ[i.first]==0){
                    Q.push(i.first);
                    InQ[i.first]=1;
                }
            }
    }
    for(int i=2;i<=N;i++)
        fout<<DP[i]<<" ";
    fout<<'\n';
}

int main(){
    fin>>N>>M;
    for(int i=1;i<=M;i++){
        int X,Y,Z;
        fin>>X>>Y>>Z;
        G[X].push_back({Y,Z});
    }
    for(int i=1;i<=N;i++)
        DP[i]=oo;
    Bellman_Ford();
    return 0;
}