#include <fstream>
#include <deque>
#include <vector>
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

struct nod{
    int a,cost;
};
deque<int> q;
int frv[50001],frv1[50001],dist[50001];
vector<vector<nod>> v;

int main()
{
    int n,m,a,b,cost,i,nod;
    cin>>n>>m;
    v.resize(n+1);
    for(i=1;i<=m;i++){
        cin>>a>>b>>cost;
        v[a].push_back({b,cost});
    }
    for(i=1;i<=n;i++) dist[i]=1e9;
    dist[1]=0;q.push_back(1);

    while(!q.empty()){
        nod=q.front();
        frv1[nod]++;
        if(frv1[nod]>n){cout<<"Ciclu negativ!";return 0;}
        q.pop_front();frv[nod]=0;
        for(i=0;i<v[nod].size();i++){
            if(dist[nod]+v[nod][i].cost<dist[v[nod][i].a]){
                if(!frv[nod]){
                    q.push_back(v[nod][i].a);frv[nod]=1;
                }
                dist[v[nod][i].a]=dist[nod]+v[nod][i].cost;
            }
        }

    }
    for(i=2;i<=n;i++) cout<<dist[i]<<" ";
    return 0;
}