#include <bits/stdc++.h>
#define FOR(i, st, dr) for(i = st; i <= dr; i++)
#define pii pair<int,int>
//#define fin cin
//#define fout cout

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int NMAX = 1e5 + 5, INF = 1e9;
vector < pii > edges;
vector < pii > g[NMAX];
vector < int > cost;
int dist[NMAX];
int n, m;

void citire()
{
    int i;
    for(i = 0; i < NMAX; ++i)
        dist[i] = INF;

    fin >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        int a, b, c;
        fin >> a >> b >> c;
        edges.push_back({a, b});
        cost.push_back(c);
        g[a].push_back({b, c});
    }
}

bool ciclu = false;
void solve()
{
    int i, j;
    dist[1] = 0;
    queue <int> hlp;
    bitset <NMAX> inHeap(0);
    int again[NMAX] = {};

    hlp.push(1);
    inHeap[1] = 1;
    int top;

    while(!hlp.empty())
    {
        top = hlp.front();
        hlp.pop();
        inHeap[top] = 0;
        again[top]++;
        if(again[top] >= n)
        {
            ciclu = true;
            return;
        }

        for(auto &it: g[top])
        {
            if(dist[top] + it.second < dist[it.first])
            {
                dist[it.first] = dist[top] + it.second;
                if(inHeap[it.first] == 0)
                    hlp.push(it.first), inHeap[it.first] = 1;
            }
        }
    }
}

int main()
{
    citire();
    solve();

    if(ciclu == true)
        fout << "Ciclu negativ!";
    else for(int i = 2; i <= n; ++i) fout << dist[i] << ' ';

    return 0;
}