#include <bits/stdc++.h>

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

//vector <pair<int, pair<int, int>>> muchii[250005];
vector <pair<int, int>> g[50005];
int dist[50005];
int n, m;
int bellman (int src)
{
    dist[src]=0;
    for (int i=1; i<=n-1; i++) {
        for (int nod=1; nod<=n; nod++) {
            for (pair <int, int> muchie: g[nod]) {
                int dest=muchie.second;
                int cost=muchie.first;
                if (dist[nod]+cost<dist[dest]) {
                    dist[dest]=dist[nod]+cost;
                }
            }
        }
    }
    for (int nod=1; nod<=n; nod++) {
        for (pair <int, int> muchie: g[nod]) {
            int dest=muchie.second;
            int cost=muchie.first;
            if (dist[nod]+cost<dist[dest]) {
                return -1;
            }
        }
    }
    return 1;
}

int main()
{
    int x, y, z;
    fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>x>>y>>z;
        g[x].push_back({z, y});
    }
    for (int i=1; i<=n; i++) {
        dist[i]=1005;
    }
    int rez=bellman(1);
    if (rez==-1) {
        fout<<"Ciclu negativ!";
        return 0;
    }
    for (int i=2; i<=n; i++) {
        fout<<dist[i]<<' ';
    }
    return 0;
}