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

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

vector<pair<int, int> > G[nmax];
int N, M, app[nmax], dist[nmax], A, B, C;
bool InQueue[nmax];

int BF();


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", &A, &B, &C);
          G[A].pb(mp(B, C));
    }
    if(BF() == 1) printf("Ciclu negativ!");
    else for(i = 2; i <= N; i++) printf("%i ", dist[i]);
    scanf("%i", &i);
    return 0;
}

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