#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define NMAX 50005
#define inf 1<<30

using namespace std;

int N, M;
vector <pair <int, int> > v[NMAX];
queue <int> q;
int dist[NMAX], nr[NMAX];
bool viz[NMAX];

void dijkstra(){
    int ciclu = 0;
    for(int i = 1; i <= NMAX; ++i)
        dist[i] = inf;
    //memset(dist, inf, sizeof(dist));
    memset(viz, 0, sizeof(viz));
    q.push(1);
    dist[1] = 0;
    viz[1] = 1;
    while(!q.empty() && !ciclu){
        int nod = q.front();
        viz[nod] = 0;
        q.pop();
        for(vector <pair<int, int> > :: iterator it = v[nod].begin(); it != v[nod].end(); ++it)
            if(dist[nod] + it->second < dist[it->first]){
                dist[it->first] = dist[nod] + it->second;
                if(!viz[it->first]){
                    if(nr[it->first] > N)
                        ciclu = 1;
                    else{
                        q.push(it->first);
                        viz[it->first] = 1;
                        ++nr[it->first];
                    }
                }
            }
    }
    if(ciclu)
        printf("Ciclu negativ!\n");
    else
    for(int i = 2; i <= N; ++i)
        printf("%d ", dist[i] == inf ? 0 : dist[i]);
}

int main(){
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int x, y, c;
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= M; ++i){
        scanf("%d %d %d", &x, &y, &c);
        v[x].push_back(make_pair(y,c));
    }
    dijkstra();
    return 0;
}