#include <fstream>
#include <queue>
using namespace std;

#define MAX 50005
ifstream cin ("bellmanford.in");
ofstream cout ("bellmanford.out");

struct Muchie
{
    int nod, cost;
};

int n, m;
int u, v, cost;
int dp[MAX];
int freq[MAX];
bool ok[MAX];
vector <Muchie> adj[MAX];
const int INF = 1e9;

bool bf(int nod)
{
    for (int i = 1; i <= n; i++)
    {
        dp[i] = INF;
    }

    queue <Muchie> q;

    dp[nod] = 0;
    q.push({nod, dp[nod]});

    while (!q.empty())
    {
        Muchie curent = q.front();
        q.pop();

        ok[curent.nod] = false;
        if (freq[curent.nod] > n) return false;

        for (const Muchie& x : adj[curent.nod])
        {
            if (dp[x.nod] > dp[curent.nod] + x.cost)
            {
                dp[x.nod] = dp[curent.nod] + x.cost;
                if (!ok[x.nod])
                {
                    ok[x.nod] = true;
                    q.push({x.nod, dp[x.nod]});
                }

            }
        }
    }

    return true;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> cost;
        adj[u].push_back({v, cost});
    }

    if (!bf(1)) cout << "Ciclu negativ!\n";
    else
    {
        for( int i = 2; i <= n; i++)
        {
            if (dp[i] == INF) cout << 0 << " ";
            else cout << dp[i] << " ";
        }
    }
    return 0;
}