#include <cstdio>
#include <vector>

FILE *fin = fopen("bellmanford.in", "r");
FILE *fout = fopen("bellmanford.out", "w");

#define maxn 500000
#define maxc 260000000
#define ll long long
#define maxm 250000

struct str {
    int a;
    int c;
};

std::vector<str> v[maxm + 1];

int d[maxn + 1];
int q[maxn + 1];
ll st = 0;
ll dr = 0;
ll dist[maxn + 1];


inline void add (int t) {
    q[dr % maxn] = t;
    d[t]++;
    dr++;

}
inline void del () {
    st++;
}


int main()
{
    int n, m, x;
    str y;
    fscanf(fin, "%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        fscanf(fin, "%d%d%d", &x, &y.a, &y.c);
        v[x].push_back (y);

    }
    for (int i = 2; i <= n; i++)
        dist[i] = maxc;

    add(1);
    d[1] = 1;
    while(st != dr) {
        for (auto y : v[q[st % maxn]]) {

            if (d[y.a] <= n) {
                if (dist[y.a] > dist[q[st % maxn]] + y.c) {
                    add(y.a);
                    dist[y.a] = dist[q[st % maxn]] + y.c;
                }
            }
            else {
                fprintf(fout, "Ciclu negativ!");
                return 0;
            }
        }
        del();
    }
    for (int i = 2; i <= n; i++) {
        fprintf(fout, "%lld", dist[i]);
        fprintf(fout, " ");
    }
    return 0;
}