#include <bits/stdc++.h>
#define inf 250000000

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector<pair<int,int>> v[50005];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> h;

int n,m,d[50005],use[50005],viz[50005],nr[50005];

int main() {
    int i,j,x,y,z;
    f>>n>>m;
    for(i=1;i<=m;i++) {
        f>>x>>y>>z;
        v[x].push_back(make_pair(z,y));
    }
    for (i=1;i<=n;i++)
        d[i]=inf;
    d[1]=0;
    h.push(make_pair(0,1));
    while (!h.empty()) {
        x=h.top().second;
        h.pop();
        viz[x]=0;
        if (!use[x])
            for (i=0;i<v[x].size();i++)
                if (v[x][i].first+d[x]<d[v[x][i].second]) {
                    d[v[x][i].second]=v[x][i].first+d[x];
                    h.push(make_pair(d[v[x][i].second],v[x][i].second));
                    if (!viz[v[x][i].second])
                        if (nr[v[x][i].second]>n) {
                            g<<"Ciclu negativ!";
                            return 0;
                        }
                        else {
                            nr[v[x][i].second]++;
                            viz[v[x][i].second]=1;
                        }
                }
        use[x]=1;
    }
    for (i=2;i<=n;i++)
        g<<d[i]<<' ';
    return 0;
}