#include <bits/stdc++.h>
#define readFast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define nl cout << '\n'
#define afis(v) for (auto x : v) {cout << x << " ";} cout << '\n';
#define afisPii(v) for (auto x : v) {cout << x.first << " " << x.second << '\n';} cout << '\n';
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 50005;

vector<pair<int,int>> graf[N];
int n, m, drum[N];
bool in[N], cicluNegativ = false;
deque<int> coada;

void bfs(int nod) {
    coada.push_back(nod);
    drum[nod] = 0;
    while(!coada.empty()) {
        nod = coada.front();
        coada.pop_front();
        in[nod] = false;

        for (pair<int,int> x : graf[nod]) {
            int to = x.first, c = x.second;
            if(drum[to] > drum[nod] + c) {
                drum[to] = drum[nod] + c;

                if(in[to] == false) {
                    in[to] = true;
                    if(drum[to] > 0)
                        coada.push_back(to);
                    else
                        coada.push_front(to);
                }
            }
        }
    }
}

int main() {
    //ifstream fin("date.in.txt");
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        graf[a].push_back({b, c});
    }
    fill(drum, drum + N, 1000000);
    bfs(1);

    if(cicluNegativ)
        cout << "Ciclu negativ!";
    else {
        for (int i = 2; i <= n; ++i)
            fout << drum[i] << " ";
    }

    return 0;
}