#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50002
#define INF 100000000
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
struct arc
{
    int x, c;
};

vector <arc> arce[NMAX];
queue <int> q;
bool neg;
int n, m, start=1;
int cmin[NMAX];
int nr[NMAX];
void citire();
void bellman();
int main()
{int i;
    citire();
    bellman();
    if (neg)
        fout<<"Ciclu negativ!";
    else {
        for (i=2; i<=n; i++)
            fout<<cmin[i]<<' ';
    }
    return 0;
}
void citire()
{
    arc vf;
    int i, x, y, cost;
    fin>>n>>m;
    for (i=1; i<=m; i++) {
        fin>>x>>y>>cost;
        vf.x=y;
        vf.c=cost;
        arce[x].push_back(vf);
    }
}
void bellman()
{   int i, vf, cost, x;
    for (i=1; i<=n; i++)
        cmin[i]=INF;
    cmin[1]=0;
    q.push(1);
    while (!q.empty()) {
        x=q.front();
        q.pop();
        for (i=0; i<arce[x].size(); i++) {
            vf=arce[x][i].x;
            cost=arce[x][i].c;
            if (cmin[vf]>cmin[x]+cost) {
                cmin[vf]=cmin[x]+cost;
                nr[vf]++;
                if (nr[vf]>=n) {
                    neg=1; break;
                }
                else
                    q.push(vf);
            }
        }
    }
}