#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
typedef pair<int, int> PII;
const int Nmax = 50005;
const int INF = 0x3f3f3f3f;

int step[Nmax];
int dist[Nmax];
vector<PII> G[Nmax];
char inQue[Nmax];

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

    int N, M, a, b, d;
    f >> N >> M;
    for (int i = 0; i < M; i++)
    {
        f >> a >> b >> d;
        G[a].push_back(make_pair(b, d));
    }

    memset(step, 0, sizeof(step));
    memset(dist, INF, sizeof(dist));
    memset(inQue, 0, sizeof(inQue));

    dist[1] = 0;
    queue<int> Q;
    Q.push(1);
    inQue[1] = 1;

    while(!Q.empty())
    {
        int a = Q.front();  Q.pop();
        if (step[a] >= N)
        {
            g << "Ciclu negativ!\n";
            return 0;
        }
        
        inQue[a] = 0;
        
        for (auto P: G[a])
        {
            if (dist[P.first] > dist[a] + P.second)
            {
                dist[P.first] = dist[a] + P.second;
                step[P.first] = step[a] + 1;
                if (!inQue[P.first])
                {
                    Q.push(P.first);
                    inQue[P.first] = 1;
                }
            }
        }
    }
    
    for (int a = 2; a <= N; a++)
        g << dist[a] << ' ';
    g << '\n';

    return 0;
}