#include <bits/stdc++.h>

struct edge
{
    int v, cost;
};

int nodes, edges, u, v, cost;

std :: vector<edge> adj[50001];

int distance[50001], visited[50001], OO = (1 << 31) - 1;

bool inQueue[50001];

struct orderByDistance
{
    bool operator()(int x, int y)
    {
        return distance[x] > distance[y];
    }
};

std :: priority_queue<int, std :: vector<int>, orderByDistance> Q;

bool Dijkstra(int source)
{
    for(int i = nodes; i; --i)
    {
        distance[i] = OO;
    }

    distance[source] = 0;

    Q.push(source);

    inQueue[source] = true;

    while(!Q.empty())
    {
        int u = Q.top(); Q.pop();

        inQueue[u] = false;

        for(edge i : adj[u])
        {
            int v = i.v, cost = i.cost;

            if(distance[v] > distance[u] + cost)
            {
                if(++visited[v] == nodes)
                {
                    return false;
                }

                distance[v] = distance[u] + cost;

                if(!inQueue[v])
                {
                    Q.push(v);

                    inQueue[v] = true;
                }
            }
        }
    }

    return true;
}

#define bufs 1000000
#define nxt() {pos++;\
    if(pos >= bufs)\
    {\
        fread(buf, 1, bufs, stdin);\
        pos = 0;\
    }\
}

char buf[bufs];
int pos = bufs;
int neg;

inline void read(int& val)
{
    neg = 0;
    while((buf[pos] < '0' || buf[pos] > '9') && buf[pos] != '-') nxt();
    if(buf[pos] == '-') { neg = 1; val = 0; }
    else val = buf[pos] - '0';
    nxt();
    while(buf[pos] >= '0' && buf[pos] <= '9') { val = val * 10 + buf[pos] - '0'; nxt(); }
    if(neg == 1) val = -val;
}

char outBuffer[5000000], *p = outBuffer;

void inline itoa(int x)
{
    if(x < 0) *p++ = 45, x = -x;

    int digits = 1;

    for(int i = x; i /= 10; ++digits);

    for(int i = digits - 1; ~i; --i)
    {
        *(p + i) = x % 10 + 48, x /= 10;
    }

    p += digits; *p++ = ' ';
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    ///freopen("bellmanford.out", "w", stdout);

    read(nodes), read(edges);

    for(int i = edges; i; --i)
    {
        read(u), read(v), read(cost);

        adj[u].push_back({v, cost});
    }

    if(Dijkstra(1))
    {
        for(int i = 2; i <= nodes; ++i)
        {
            itoa(distance[i]);
        }

        puts(outBuffer);
    }
    else
    {
        puts("Ciclu negativ!");
    }

    return 0;
}