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

ifstream is("bellmanford.in");
ofstream os("bellmanford.out");

int N, M, x, y, z;
vector <pair<int,int> > G[50001];
int dist[50001];

struct Edge
{
    int x;
    int y;
    int z;
};

Edge edge[50001];

void Input();
void BellmanFord();

int main()
{
    Input();
    BellmanFord();

    is.close();
    os.close();
}

void Input()
{
    is >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        is >> x >> y >> z;

        edge[i].x = x;
        edge[i].y = y;
        edge[i].z = z;

        dist[i] = 0x3f3f3f3f;
    }
    dist[1] = 0;
}

void BellmanFord()
{
    for (int i = 1; i <= N + 1; ++i)
    {
        for ( int j = 1; j <= M; ++j)
        {
            int x = edge[j].x;
            int y = edge[j].y;
            int z = edge[j].z;

            if (dist[y] > z + dist[x])
            {
                if (i == N+1)
                {
                    os << "Ciclu negativ!";
                    return;
                }
                dist[y] = z + dist[x];
            }
        }
    }
    for (int i = 2; i <= N; ++i)
        os << dist[i] << " ";
}