#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define nmax 50010
#define pb push_back
#define mp make_pair
#define to first
#define cost second

int used[nmax], app[nmax], N, M, X, Y, C, cost[nmax];
bool InQueue[nmax];
vector<pair<int, int> > G[nmax];


int BellmanFord();


int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int i;
    scanf("%i %i", &N, &M);
    for(i = 1; i <= M; i++)
    {
          scanf("%i %i %i", &X, &Y, &C);
          G[X].pb(mp(Y, C));
    }
    if(BellmanFord() == 0) printf("Ciclu negativ!\n");
    else for(i = 2; i <= N; i++) printf("%i ", cost[i]);
    return 0;
}

int BellmanFord()
{
     int i, node = 1;
     vector<pair<int, int> > :: iterator it;
     for(i = 1; i <= N; i++) cost[i] = 0x3f3f3f3f;
     cost[1] = 0;
     app[1] = 1;
     queue<int> Q;
     InQueue[1] = true;
     Q.push(1);
     while(!Q.empty())
     {
                      node = Q.front(); Q.pop();
                      InQueue[node] = false;
                      if(app[node] > N) return 0;
                      for(it = G[node].begin(); it != G[node].end(); ++it)
                             if(cost[it -> to] > cost[node] + it -> cost)
                             {
                                        cost[it -> to] = cost[node] + it -> cost;
                                        if(!InQueue[it -> to])
                                        {
                                                       InQueue[it -> to] = true;
                                                       app[it -> to] ++;
                                                       Q.push(it -> to);
                                        }
                             }
     }
     return 1;
}