#include <bits/stdc++.h>

using namespace std;

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

//vector <pair<int, pair<int, int>>> muchii[250005];
list <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++) {
            vector <list <pair<int, int>>::iterator> trash;
            for (auto it=g[nod].begin(); it!=g[nod].end(); it++) {
                pair <int, int> muchie = *it;
                int dest=muchie.second;
                int cost=muchie.first;
                if (dist[nod]+cost<dist[dest]) {
                    dist[dest]=dist[nod]+cost;
                }
                else if (dist[nod]!=1005) {
                    trash.push_back(it);
                }
            }
            for (auto it: trash) {
                //cout<<"Erasing: "<<it->first<<endl;
                g[nod].erase(it);
            }
        }
    }
    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;
}