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

using namespace std;

const int MAXN = 50041;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m;
vector<pair<int, int> > graf[MAXN];
int dmin[MAXN];


void citire()
{
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        //graf[x].push_back({y, c});
        graf[x].push_back(make_pair(y, c));
    }
    for (int i = 1; i <= n; i++)
        dmin[i] = 0x3f3f3f3f;
}

queue<int> q;
bool inq[MAXN];
int cnt[MAXN];

bool bellman()
{
    q.push(1);
    inq[1] = true;
    cnt[1] = 1;
    dmin[1] = 0;

    while (!q.empty()) {
        int top = q.front();
        q.pop();
        inq[top] = false;
        for (const auto& vecin : graf[top]) {
            if (dmin[vecin.first] > dmin[top] + vecin.second) {
                dmin[vecin.first] = dmin[top] + vecin.second;
                if (!inq[vecin.first]) {
                    inq[vecin.first] = true;
                    q.push(vecin.first);
                    if (++cnt[vecin.first] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

int main() {

    citire();
    if (!bellman())
        fout << "Ciclu negativ!";
    else
        for (int i = 2; i <= n; i++)
            fout << dmin[i] << " ";

    return 0;
}