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

using namespace std;

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

const int NMAX = 5 * (1e5);

struct edge
{
    int dest, cost;
};

vector <edge> graph[NMAX + 5];
queue <int> q;
int fr[NMAX + 5], n, dp[NMAX + 5];

bool bfs()
{
    q.push(1);

    while(!q.empty())
    {
        int curr = q.front();
        q.pop();

        fr[curr]++;

        if(fr[curr] == n + 1)
            return false;

        for(auto neigh : graph[curr])
        {
            if(dp[neigh.dest] > dp[curr] + neigh.cost)
            {
                dp[neigh.dest] = dp[curr] + neigh.cost;

                q.push(neigh.dest);
            }
        }
    }

    return true;
}

int main()
{
    int m;
    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;

        edge e;
        e.dest = y;
        e.cost = c;

        graph[x].push_back(e);
    }

    dp[1] = 0;
    for(int i = 2; i <= n; i++)
        dp[i] = INT_MAX;

    if(bfs() == false)
        fout << "Ciclu negativ!";
    else for(int i = 2; i <= n; i++)
            fout << dp[i] << ' ';

    fin.close();
    fout.close();
    return 0;
}