#include <bits/stdc++.h>
#define DM 50005
#define pii pair<int,int>
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int best[DM],it[DM],n,m,a,b,c;
vector<pii> v[DM];

void bf(int i){
    it[i]++;
    if(it[i]==n)
    {
        fout<<"Ciclu negativ!";
        exit(0);
    }
    for(int j=0;j<v[i].size();++j)
        if(best[v[i][j].x]>v[i][j].y+best[i]){
            best[v[i][j].x]=v[i][j].y+best[i];
            bf(v[i][j].x);
        }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i){
        fin>>a>>b>>c;
        v[a].pb({b,c});
    }
    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;
}