#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m;
int st, dr, c;
vector<pair<int,int>> v[50001];
int mark[50001];
int ct[50001];
bool ok = 1, mark2[50001];

void bf(int start){
    mark[start] = 1;
    queue<pair<int,int>> q;
    q.push({1, start});
    while(!q.empty()){
        int cost_curr = q.front().first;
        int nod_curr = q.front().second;
        q.pop();
        if (cost_curr != mark[nod_curr])
            continue;
        for (int i = 0; i < v[nod_curr].size(); i++){
            int vecin = v[nod_curr][i].first;
            int cost = v[nod_curr][i].second;
            if ((!mark2[vecin] || mark[nod_curr] + cost < mark[vecin]) && ct[vecin] <= n - 1){
                mark[vecin] = mark[nod_curr] + cost;
                mark2[vecin] = 1;
                q.push({mark[vecin], vecin});
                ct[vecin]++;
            }
            else if (ct[vecin] > n - 1){
                fout << "Ciclu negativ!";
                ok = 0;
                return;
            }
        }
    }
}

int main(){
fin>>n>>m;
for (int i = 1; i <= m; i++){
    fin>>st>>dr>>c;
    v[st].push_back({dr, c});
}
bf(1);
for (int i = 2; i <= n && ok == 1; i++){
    if (!mark2[i])
        fout << 0 << " ";
    else
        fout << mark[i] - 1 << " ";
}
// complexitate O(m*n)
    return 0;
}