#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 nrvizitari[NMAX];


bool bellmanford(){


q.push(1);

while(!q.empty()){

    int nod=q.top();
    q.pop();
    nrvizitari[nod]++;
    if(nrvizitari[nod]>=n)
        return false;


    for(size_t i=0;i<graf[nod].size();i++){
        int vecin=graf[nod][i].first;
        int cost=graf[nod][i].second;
        if(cost+dist[nod]<dist[vecin]){
            dist[vecin]=dist[nod]+cost;
                q.push(vecin);

        }

    }

}


return 1;
}



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;


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