#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

#define MAX_N 50005
#define INF 0x3f3f3f3f

int n, m;
vector <pair<int, int> > g[MAX_N];
int d[MAX_N];
int c[MAX_N];
int t[MAX_N];

int main () {
    freopen ("bellmanford.in", "r", stdin);
    freopen ("bellmanford.out", "w", stdout);
    
    scanf ("%d %d", &n, &m);
    
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        scanf ("%d %d %d", &a, &b, &c);
        
        g[a].push_back (make_pair (b, c));
    }
    
    memset (d, INF, sizeof (d));    
    queue<int> Q;
    
    t[1] = 1;
    c[1] = 1;
    d[1] = 0;
    Q.push (1);
    
    while (!Q.empty()) {
          int node = Q.front(); Q.pop();
          t[node] = 0;
          
          for (int i = 0; i < (int)g[node].size(); ++i)
              if (d[g[node][i].first] > d[node] + g[node][i].second) {
                    d[g[node][i].first] = d[node] + g[node][i].second;
                    
                    if (!t[g[node][i].first]) {
                         Q.push (g[node][i].first);
                         ++c[g[node][i].first];
                         t[g[node][i].first] = 1;
                    }
                    
                    if (c[g[node][i].first] > n) {
                        printf ("Ciclu negativ!\n");
                        return 0;
                    }
              }
    }
    
    for (int i = 2; i < n; ++i) printf ("%d ", d[i]);
    printf ("%d\n", d[n]);
    
    return 0;
}