#include<bits/stdc++.h>
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int INF = 1e9;

int n, m, i, a, b, c, x;
vector<pair<int,int>> graf[1001];
int dist[1001];
bool incoada[1001];
int cnt[1001];

int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i++)
    {
        f >> a >> b >> c;
        graf[a].push_back({b, c});
    }

    for(i = 1; i <= n; i++)
    {
        dist[i] = INF;
        incoada[i] = false;
        cnt[i] = 0;
    }

    int sursa = 1;
    dist[sursa] = 0;

    queue<int> q;
    q.push(sursa);
    incoada[sursa] = true;
    cnt[sursa] = 1;

    while(!q.empty())
    {
        x = q.front();
        q.pop();
        incoada[x] = false;

        for(auto it : graf[x])
        {
            int y = it.first;
            int cost = it.second;

            if(dist[x] + cost < dist[y])
            {
                dist[y] = dist[x] + cost;

                if(!incoada[y])
                {
                    q.push(y);
                    incoada[y] = true;
                    cnt[y]++;

                    if(cnt[y] > n)
                    {
                        g << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for(i = 2; i <= n; i++)
    {
        if(dist[i] == INF)
            g << "0 ";
        else
            g << dist[i] << " ";
    }

    return 0;
}