#include <bits/stdc++.h>
#define Nmax 50002
#define pii pair <int, int>
#define f first
#define s second
#define INF 2000000005
#define pb(x) push_back(x)
FILE *fin  = freopen("bellmanford.in", "r", stdin);
FILE *fout = freopen("bellmanford.out", "w", stdout);

using namespace std;
int n, m, A[2][Nmax];
vector <pii> G[Nmax];
void read()
{
    int u, v, w;
    scanf("%d %d", &n, &m);
    while(m --)
    {
        scanf("%d %d %d", &u, &v, &w);
        G[v].pb(pii(u, w));
    }
}
void solve()
{
    int i, j, v, u, c;
    memset(A[0], INF, sizeof(A[0]));
    A[0][1] = 0;
    for(i = 1; i <= n; ++ i)
    {
        memset(A[i & 1], INF, sizeof(A[i & 1]));
        for(v = 1; v <= n; ++ v)
        {
            A[i & 1][v] = A[(i - 1) & 1][v];
            int sz = G[v].size();
            for(j = 0; j < sz; ++ j)
            {
                u = G[v][j].f;
                c = G[v][j].s;
                if(A[i & 1][v] > A[(i - 1) & 1][u] + c)
                {
                    /// test for negative cycle
                    if(i == n)
                    {
                        printf("Ciclu negativ!\n");
                        exit(0);
                    }
                    A[i & 1][v] = A[(i - 1) & 1][u] + c;
                }
            }
        }
    }
}
void write()
{
    for(int i = 2; i <= n; ++ i)
        printf("%d ", A[(n - 1) & 1][i]);
    printf("%\n");
}
int main()
{
    read();
    solve();
    write();
    return 0;
}