#include <bits/stdc++.h>
#define DM 5005
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
bitset<DM>leg[DM];
int mt[DM][DM],best[DM],it[DM],n,m,a,b,c;

void bf(int i){
    it[i]++;
    if(it[i]==n)
    {
        fout<<"Ciclu negativ!";
        exit(0);
    }
    for(int j=1;j<=n;++j){
        if(j==i) continue;
        if(leg[i][j]){
            if(best[j]>mt[i][j]+best[i])
            {
                best[j]=mt[i][j]+best[i];
                bf(j);
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i){
        fin>>a>>b>>c;
        mt[a][b]=c;
        leg[a][b]=1;
    }
    for(int i=2;i<=n;++i) best[i]=INT_MAX;
    bf(1);
    for(int i=2;i<=n;++i)fout<<best[i]<<" ";
    return 0;
}