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

using namespace std;

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

#define Gmax 100010
#define INF 0x3f3f3f3f

vector < pair <int,int> > G[Gmax];
queue < pair<int,int> > q;
int dist[Gmax];


int main()
{
    int N,M;
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }

    memset( dist, 0x3f, sizeof(dist));
    q.push(make_pair(1,0));
    bool notFirst = false;
    while(!q.empty())
    {
        int nod = q.front().first;
        int d = q.front().second;
        q.pop();
        /// this cuz i need to see the cycle and return neg cycle

        if(nod == 1 && notFirst)
            if(d < 0) {
                g<<"Ciclu negativ!";
                return 0;
            }else break;

        /*
        if(dist[nod] != INF)
            continue;
        */
        ///end cuz need cycle
        dist[nod] = d;
        notFirst = true;
        for(int i=0;i<G[nod].size();i++)
        {
            q.push(make_pair(G[nod][i].first,d + G[nod][i].second));
        }
    }

    for(int i=2;i<=N;i++)
    {
        if(dist[i] == INF)
            g<<-1<<' ';
        else
        g<<dist[i]<<' ';
    }


    return 0;
}