#include <fstream>
#include <vector>
#include <deque>
#include <bitset>
#define DIM 50010
#define INF 2000000000
using namespace std;
int n,m,i,x,y,z,D[DIM],cnt[DIM],verif;
vector<pair<int,int> >L[DIM];
deque<int> c;
bitset<DIM> viz;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
void bellman_ford(int p){
    c.push_back(p);
    viz[p]=1;
    while (!c.empty()){
        int nod=c.front();
        c.pop_front();
        viz[nod]=0;
        for (int i=0;i<L[nod].size();i++){
            int vecin=L[nod][i].first;
            int cost=L[nod][i].second;
            if (D[vecin]>D[nod]+cost){
                D[vecin]=D[nod]+cost;
                if (viz[vecin]==0){
                    cnt[vecin]++;
                    if (cnt[vecin]>=n){
                        fout<<"Ciclu negativ!";
                        verif=1;
                        return ;
                    }
                    c.push_back(vecin);
                    viz[vecin]=1;
                }
            }
        }
    }
}
void init(int *D, int x){
    for (int i=1;i<=n;i++){
        D[i]=INF;
    }
    D[x]=0;
}
int main() {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>z;
        L[x].push_back(make_pair(y, z));
    }
    init(D, 1);
    bellman_ford(1);
    if (verif==1){
        return 0;
    }
    for (i=2;i<=n;i++){
        fout<<D[i]<<" ";
    }
    return 0;
}