//ALEXANDRU MICLEA

#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

//#include <iostream>
#include <fstream>
//ifstream fin("input.in"); ofstream fout("output.out");
ifstream fin("bellmanford.in"); ofstream fout("bellmanford.out");

//VARIABLES

class cmp {
public:

    bool operator () (pair<int, int>& a, pair<int, int>& b) {
        return a.second > b.second;
    }
};

const int MAXM = 50005;

int dp[MAXM];
int vis[MAXM];
int used[MAXM];

vector < vector <pair <int, int> > > gr(MAXM);

queue <int> Q;



//FUNCTIONS



//MAIN
int main() {

    int n, m;

    fin >> n >> m;

    for (int i = 2; i <= n; i++) {
        dp[i] = 1e9;
    }

    for (int i = 1; i <= m; i++) {
        int a, b, val;

        fin >> a >> b >> val;

        gr[a].push_back({ b, val });
    }

    Q.push(1);

    while (!Q.empty()) {

        int now = Q.front();
        Q.pop();
        vis[now]++;
        used[now] = false;

        if (vis[now] > n) {
            fout << "Ciclu negativ!";
            return 0;
        }

        for (auto& x : gr[now]) {

            if (dp[x.first] > dp[now] + x.second) {
                dp[x.first] = dp[now] + x.second;

                if (!used[x.first]) {
                    Q.push(x.first);
                    used[x.first] = true;
                }
                else vis[x.first]++;
                
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        fout << dp[i] << " ";
    }

    return 0;
}