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

#define NLen 0x10000
#define inf 0x7fffffff

using namespace std;

ifstream fi;
ofstream fo;

vector < pair < int, int > > g[NLen];
int dist[NLen];
int cnt[NLen];
int use[NLen];

int N;

inline int bf(int nod)
{
    queue < int > Q;

    memset(cnt, 0, sizeof(cnt));
    memset(use, 0, sizeof(use));
    for(int i = 1;i <= N; ++ i) dist[i] = inf;

    Q.push(nod);
    dist[nod] = 0;
    use[nod] = 1;

    for(;!Q.empty();Q.pop())
    {
        nod = Q.front();
        use[nod] = 0;

        for(int i = 0;i < g[nod].size(); ++ i)
            if(dist[ g[nod][i].first ] == inf || dist[ g[nod][i].first ] > dist[nod] + g[nod][i].second)
            {
                dist[ g[nod][i].first ] = dist[nod] + g[nod][i].second;
                if(!use[ g[nod][i].first ])
                {
                    use[ g[nod][i].first ] = 1;
                    Q.push(g[nod][i].first);
                    ++ cnt[ g[nod][i].first ];

                    if(cnt[ g[nod][i].first ] >= N - 1 ) return 1;
                }
            }
    }

    return 0;
}

int main()
{
    int M, x, y, c;

    fi.open("bellmanford.in");

    fi >> N >> M;
    for( ;M -- ;)
    {
        fi >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }

    fi.close();

    fo.open("bellmanford.out");

    if(bf(1)) fo << "Ciclu negativ!";
    else
    {
        for(int i = 2;i <= N; ++ i)
            fo << dist[i] << ' ';
        fo << '\n';
    }

    fo.close();

    return 0;
}