#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
ifstream intrare("bellmanford.in");
ofstream iesire("bellmanford.out");
const int NMAX=50005;
const int inf=(1<<27);
int n,m,i,j,dist[NMAX];
vector < pair < int, int > > graf[NMAX*5];
priority_queue <int, vector < int >, greater<int> > q;
int vizitat[NMAX];


int main()
{
    intrare>>n>>m;
    int x,y,z;
    for(i=1;i<=m;i++){
        intrare>>x>>y>>z;
        graf[x].push_back(make_pair(y,z));
    }
    for(i=1;i<=n;i++)
        dist[i]=inf;

    dist[1]=0;

    for(int g=1;g<=n-1;g++)
    for(i=1;i<=n;i++)
    for(size_t j=0;j<graf[i].size();j++){
        int vecin=graf[i][j].first;
        int cost=graf[i][j].second;
        if(dist[i]!=inf && cost+dist[i]<dist[vecin])
            dist[vecin]=cost+dist[i];

                }


    bool nuex=false;
    for(i=1;i<=n;i++)
    for(size_t j=0;j<graf[i].size();j++){
        int vecin=graf[i][j].first;
        int cost=graf[i][j].second;
        if(dist[i]!=inf && cost+dist[i]<dist[vecin])
            nuex=true;
            i=n+1;
            break;

                }



if(nuex==false)
for(i=2;i<=n;i++)
    if(dist[i]==inf)
    iesire<<"0"<<" ";
else
    iesire<<dist[i]<<" ";
else
    iesire<<"Ciclu negativ!";
    return 0;
}