#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
using namespace std;

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

vector<pair<int, int> > v[50005];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > qp;
queue<int> q;
int n, m, val, a, b, p, s, cnt, x,valmin = 1e9, valmax = 0, d[50005], f[50005], xs, xd,viz[50005],in_q[50005];

int main() {
    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        fin >> a >> b >> val;
        v[a].push_back({b, val});
    }
    s=1;
    q.push(s);
    fill(d+1,d+n+1,1e9);
    d[s]=0;
    viz[s]=1;
    in_q[s]=1;
    while(!q.empty())
    {
        x=q.front();
        viz[x]=0;
        if(in_q[x]==0)
        {
            in_q[x]=1;
        }
        else{continue;}
        for(int i=0;i<v[x].size();i++)
        {
            if(d[v[x][i].first]>d[x]+v[x][i].second)
            {
                d[v[x][i].first]=d[x]+v[x][i].second;
                if(viz[v[x][i].first]==0)
                {
                    in_q[v[x][i].first]++;
                    if(in_q[v[x][i].first]>n)
                    {
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                    q.push(v[x][i].first);
                    viz[v[x][i].first]=1;
                }
            }
        }
        q.pop();
    }
    for(int i=2;i<=n;i++)
    {
        fout<<d[i]<<" ";
    }
    fin.close();
    fout.close();
    return 0;
}