#include <fstream>
#include <vector>
#include <queue>
#include <stdlib.h>
#include <set>
#include <algorithm>
using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
const int NMAX=50000;
const int inf=10000000;
int n,m;

vector<pair<int,int>> Graf[NMAX+1];
int dist[NMAX+1];
int viz[NMAX+1];
vector<int> Nciclu;
void reset()
{
    for(int i=1;i<=n;i++)
        dist[i]=inf;
}

void BellmanFord()
{
    reset();
    queue<int> q;
    q.push(1);
    dist[1]=0;
    bool ok=1;
    while(!q.empty() && ok==1)
    {
        int nod=q.front();
        q.pop();

        viz[nod]++;

        if(viz[nod]>=n)
        {
            ok=0;
            break;
        }

        for(auto adj : Graf[nod])
        {
            if(dist[adj.first] > dist[nod] + adj.second)
            {
                dist[adj.first]=dist[nod]+ adj.second;
                q.push(adj.first);
            }
        }
    }
    if(ok==0)
        fout <<  "Ciclu negativ!";
    else
    {
        for(int i=2;i<=n;i++)
        {
            fout << dist[i] << ' ';
        }
    }
}

int main()
{
    fin>> n >> m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >>c;
        Graf[x].push_back({y,c});
    }
    BellmanFord();
    return 0;
}