#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

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

const int NMax = 50005, INF = 2000000000;
int N, M;
int dist[NMax], visit[NMax], t[NMax];
queue < int > q;
vector < int > v[NMax], c[NMax];

void BellmanFord()
{
    for (int i = 2; i <= N; i++)
        dist[i] = INF;

    dist[1] = 0;
    visit[1] = 1;
    q.push(1);

    while (!q.empty())
    {
        int point = q.front();
        visit[point] = 0;
        q.pop();

        for (int i = 0; i < v[point].size(); i++)
        {
            if (dist[v[point][i]] > dist[point] + c[point][i])
            {
                dist[v[point][i]] = dist[point] + c[point][i];
                if (!visit[v[point][i]])
                {
                    if (t[v[point][i]] > N)
                    {
                        printf("Ciclu negativ!\n");
                        return;
                    }
                    else
                    {
                        visit[v[point][i]] = 1;
                        t[v[point][i]] ++;
                        q.push(v[point][i]);

                    }
                }
            }
        }
    }

    for (int i = 2; i <= N; i++)
        if (dist[i] == INF)     printf("0 ");
        else                    printf("%d ", dist[i]);
}

int main()
    {
        scanf("%d%d", &N, &M);
        for (int i = 1, X, Y, C; i <= M; i++)
        {
            scanf("%d%d%d", &X, &Y, &C);
            v[X].push_back(Y);
            c[X].push_back(C);
        }

        BellmanFord();
    }