#include <fstream>
#include <vector>
#define MAX 1 << 30

using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int n, m, d[50010];

vector < pair<int, int> > edge[50010];

int main()
{
    int i, x, y, z;
    fin >> n >> m;

    for (i = 1; i <= m; i++) {
        fin >> x >> y >> z;
        edge[x].push_back( make_pair(y, z) );
    }

    for (i = 2; i <= n; i++)
        d[i] = MAX;

    bool bellmanford = false; int r = 0;
    while (!bellmanford) {
        if (r >= n) {
            fout << "Ciclu negativ!";
            return 0;
        }
        r++;
        bellmanford = true;

        for (i = 1; i <= n; i++) {

            for (unsigned int l = 0; l < edge[i].size(); l++ ) {
                if (d[i] + edge[i][l].second < d[ edge[i][l].first ]) {
                    d[ edge[i][l].first ] = d[i] + edge[i][l].second;
                    bellmanford = false;
                }
            }

        }
    }

    for (i = 2; i <= n; i++)
        fout << d[i] << " ";
    return 0;
}