#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define max_n 50005
#define FORIT( it,v ) for(typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it )
 
int n,m;
int i,a,b,c;
 
priority_queue< pair<int,int> > Deq;
vector< pair<int,int> > Vertex[max_n];
int Best[max_n], Nr[max_n];
bool Inside[max_n]; 
 
int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d", &n, &m );
    for( i=1; i<=m; ++i ){
        scanf("%d %d %d", &a, &b, &c );
        Vertex[a].pb(mp(b,c));
    }
    for( i=1; i<=n; ++i )
        Best[i]=INF;
    Best[1]=0;
    Deq.push(mp(0,1));
    int nod,cost;
    while( !Deq.empty() ){
        nod=Deq.top().se;
        cost=Deq.top().fi;
        Inside[nod]=0;
        Deq.pop();
        if( cost == Best[nod] ){
            Nr[nod]++;
            if( Nr[nod]>n+m ){
                printf("Ciclu negativ!\n");
                return 0;
            }
            FORIT( it, Vertex[nod] ){
                if( cost+it->se < Best[it->fi] ){
                    Best[it->fi]=cost+it->se;
                    if( !Inside[ it->fi ] ){
	                    Deq.push(mp(it->se+cost,it->fi));
	                    Inside[ it->fi ]=1;
	                }
                }
            }
        }
    }
    for( i=2; i<=n; ++i ){
        printf("%d ",Best[i]);
    }
    return 0;
}