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

#define NLen 0x10000
#define inf 0x7fffffff

using namespace std;

ifstream fi;
ofstream fo;

int N;

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

class ComparePQ
{
    public:
        int operator()(const int & a, const int & b)
        {
            return dist[a] > dist[b];
        }
};

inline int bf(int nod)
{
    priority_queue < int, vector < int > , ComparePQ > PQ;

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

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

    for( ;!PQ.empty();)
    {
        nod = PQ.top();
        PQ.pop();

        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;
                    ++ cnt[ g[nod][i].first ];
                    PQ.push(g[nod][i].first);

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

    return 0;
}

int main(int argc, char * argv[])
{
    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;
}