#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;
#define N 50001
int n,m,i ,x,y,z  ;
bool used[N];
int nr[N];
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    vector<pair<int,int> > V[N];
    scanf("%d %d\n",&n,&m);
    while(m--){
        scanf("%d %d %d\n",&x,&y,&z);
        V[x].push_back( {y,z} );
    }
    int cost[N]; for(i=1;i<=n;++i) cost[i] = 1<<29;
    cost[1]=0;
    queue<int> q; q.push(1);used[1]=1;

    for(;!q.empty();q.pop()){
        x = q.front(); used[x] = 0;
        if(used[x] == 1<<29) continue;
        for(vector<pair<int,int> >::iterator it=V[x].begin(); it != V[x].end(); ++it){
            if( cost[x]+it->second < cost[it->first] ){
                cost[it->first] =cost[x]+it->second ;
                if( !used[it->first] ){
                    if(nr[it->first]>n){
                        printf("Ciclu negativ!");
                        return 0;
                    }
                    q.push(it->first);
                    used[it->first ]=1;
                    nr[it->first]++;
                }
            }
        }
    }
    for (i=2;i<=n;i++) printf("%d ",cost[i]);


    return 0;
}