/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");

const int INF = 2e9;
const int N = 5e4;
const int M = 25e4;

vector <pair <int, int>> G[1 + N];
int dist[1 + N];
bitset <1 + N> inqueue;
int n, m;

void BellmanFord() {
  int cnt;

  for(int i = 1; i <= n; i++) dist[i] = INF;
  dist[1] = 0;
  inqueue[1] = true;

  queue <int> q;
  q.push(1);
  cnt = 1;

  while(q.size() && cnt <= n * m) {
    int from = q.front();
    inqueue[from] = false;
    q.pop();
    
    for(pair <int, int> e : G[from]) {
      if(dist[from] + e.second < dist[e.first]) {
        dist[e.first] = dist[from] + e.second;
        if(inqueue[e.first] == false) {
          q.push(e.first);
          inqueue[e.first] = true;
        }
      }
    }

    ++cnt;
  }

  if(cnt > n * m) {
    out << "Ciclu negativ!\n";
    exit(0);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  in.tie(nullptr); out.tie(nullptr);
  in >> n >> m;
  for(int i = 1; i <= m; i++) {
    int x, y, w;
    in >> x >> y >> w;
    G[x].push_back(make_pair(y, w));
  }

  BellmanFord();
  for(int i = 2; i <= n; i++)
    out << dist[i] << ' ';  
  return 0;
}