#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

const int NMAX = 50000;
const int INF = 1e9;

int N, M;
vector < pair<int,int> > g[NMAX + 5];

int dist[NMAX + 5], impr[NMAX + 5];
bool inQ[NMAX + 5];

int main()
{
    cin >> N >> M;

    for(int i = 1; i <= M; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        g[x].push_back({y, c});
    }

    for(int i = 1; i <= N; i++)
        dist[i] = INF;

    queue <int> Q;
    Q.push(1); dist[1] = 0; inQ[1] = true;

    while(!Q.empty()) {
        int node = Q.front();
        Q.pop();
        inQ[node] = false;

        for(auto it : g[node])
            if(dist[it.first] > it.second + dist[node]) {
                dist[it.first] = it.second + dist[node];

                if(!inQ[it.first]) {
                    Q.push(it.first);
                    inQ[it.first] = true;

                    impr[it.first]++;
                    if(impr[it.first] > N) {
                        cout << "Ciclu negativ!\n";
                        return 0;
                    }
                }
            }
    }

    for(int i = 2; i <= N; i++)
        cout << dist[i] << ' ';

    return 0;
}