#include <cstdio>
#include <cstdlib>
#include <queue>
#define MaxN 50005
#define Inf 1001
using namespace std;
struct Pair{
    int V;
    int C;
};
int Dist[MaxN], Count[MaxN], i, N, M, j;
bool InQ[MaxN];
queue<int> Q;
Pair *List[MaxN];
void Read();
void BellFord(int i);
int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    Read();
    BellFord(1);
    for(i=2; i<=N; ++i)printf("%d ", Dist[i]);
    return 0;
}
void Read(){
    scanf("%d%d", &N, &M);
    for(i=1; i<=N; ++i){
        List[i]=(Pair *)realloc(List[i], sizeof(Pair));
        List[i][0].V=List[i][0].C=0;
        Dist[i]=Inf;
    }
    for(i=1; i<=M; ++i){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        ++List[x][0].V; ++List[x][0].C;
        List[x]=(Pair *)realloc(List[x], (List[x][0].V+1)*sizeof(Pair));
        List[x][List[x][0].V].V=y;
        List[x][List[x][0].C].C=z;
    }
    return;
}
void BellFord(int i){
    int j; Q.push(i); Dist[i]=0; InQ[i]=true;
    while(!Q.empty()){
        int P=Q.front();
        Q.pop();
        InQ[P]=false;
        ++Count[P];
        if(Count[P]==N){
            printf("Ciclu negativ!");
            exit(EXIT_SUCCESS);
        }
        for(j=1; j<=List[P][0].V; ++j){
            int V=List[P][j].V, C=List[P][j].C;
            if(Dist[P]+C<Dist[V] && InQ[V]==false) {Dist[V]=Dist[P]+C; InQ[V]=true; Q.push(V);}
            else if(Dist[P]+C<Dist[V]) Dist[V]=Dist[P]+C;
        }
    }
    return;
}