#include <iostream>
#include <bits/stdc++.h>
#define N 50005
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector<pair<int, int>> adj[N];
int n,m;
int D[N];
int tata[N];
int vis[N];
int visneg[N];  // daca am ciclu negativ
bool negcycle = false;
queue<pair<int,int>> q;

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        adj[x].push_back({y,z});
    }
}


void Bellman_Ford()
{
    for (int i = 1; i <= n; i++)
        D[i] = 1e9;
    D[1] = 0;
    q.push({1,0});
    vis[1] = 1;

    while (!q.empty())
    {
        int nod = q.front().first;
        int cost = q.front().second;
        q.pop();
        visneg[nod] ++;
        if(visneg[nod] > n)
        {
               negcycle = true;
            return;
        }
        vis[nod] = 0;

        for (auto vecin : adj[nod])
        {
            int vec = vecin.first;
            int cost_vecin = vecin.second;

            if (D[vec] > D[nod] + cost_vecin)
            {
                D[vec] = D[nod] + cost_vecin;
                tata[vec] = nod;
                if (!vis[vec])
                {
                    q.push({vec, D[vec]});
                    vis[vec] = 1;
                }
            }

        }

    }

}


int main() {
    citire();
    Bellman_Ford();
    if(negcycle)
        fout<<"Ciclu negativ!";
    else
    {
        for(int i=2;i<=n;i++)
            fout<<D[i]<<" ";
    }

    return 0;
}