#include <fstream>
#include <vector>
#include <queue>
#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];
queue <int> Q;

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;
    Q.push(1);

    bool inqueue[50010] = {false}; int cnt_inqueue[50010] = {0};

    inqueue[1] = true; cnt_inqueue[1] = 1;
    while ( !Q.empty() ) {

        int nod = Q.front();
        Q.pop();
        inqueue[nod] = false;

        for (unsigned int l = 0; l < edge[ nod ].size(); l++ ) {

            if (d[nod] + edge[nod][l].second < d[ edge[nod][l].first ]) {
                d[ edge[nod][l].first ] = d[nod] + edge[nod][l].second;
                if ( !inqueue[ edge[nod][l].first ] ) {

                    if ( cnt_inqueue[ edge[nod][l].first ] > n) {
                        fout << "Ciclu negativ!";
                        return 0;
                    }

                    Q.push ( edge[nod][l].first );
                    inqueue[ edge[nod][l].first ] = true;
                    cnt_inqueue[ edge[nod][l].first ]++;
                }
            }
        }

    }

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