#include <fstream>
#include <bitset>
#include <queue>

using namespace std;

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

const int MAX_N = 50000;
const int INF = 1 << 30;

struct Edge
{
    int next, cost;
};

vector<Edge> adj[MAX_N + 1];
bitset<MAX_N + 1> inQueue;
int dist[MAX_N + 1];
queue<int> q;
int n, m;

void ReadGraph()
{
    fin >> n >> m;
    while(m--)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        adj[x].push_back({ y, cost });
    }
}

void Init(int src)
{
    for(int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[src] = 0;
}

bool BellmanFord(int src)
{
    Init(src);
    q.push(src);
    inQueue[src] = true;
    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        inQueue[node] = false;
        for(Edge edge : adj[node])
            if(!inQueue[edge.next] && dist[edge.next] > dist[node] + edge.cost)
            {
                dist[edge.next] = dist[node] + edge.cost;
                q.push(edge.next);
                inQueue[edge.next] = true;
            }
    }
    for(int node = 1; node <= n; node++)
        for(Edge edge : adj[node])
            if(dist[edge.next] > dist[node] + edge.cost)
                return false;
    return true;
}

void Solve(int src)
{
    bool res = BellmanFord(src);
    if(!res)
        fout << "Ciclu negativ!\n";
    else
    {
        for(int i = 1; i <= n; i++)
            if(i != src)
                fout << dist[i] << ' ';
        fout << '\n';
    }
}

int main()
{
    ReadGraph();
    Solve(1);

    fin.close();
    fout.close();

    return 0;
}