#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 5e4 + 5;
const int inf = (1 << 30);


int cnt[nmax];
int ans[nmax];
bool fv[nmax];

vector <pair <int, int> > neigh[nmax];

int main()
{
   int n, m;
   f >> n >> m;
   for (int i = 1; i <= m; ++ i)
   {
       int u, v, cost;
       f >> u >> v >> cost;
       neigh[u].emplace_back(v, cost);
   }
   for (int node = 2; node <= n; ++ node)
       ans[node] = inf;
   ans[1] = 0;
   cnt[1] = 1;
   queue <int> Q;
   Q.push(1);
   while (!Q.empty())
   {
       int now = Q.front();
       Q.pop();
       fv[now] = 0;
       if (cnt[now] > n)
       {
           g << "Ciclu negativ!";
           return 0;
       }
       for (auto edge : neigh[now])
       {
           int next = edge.first;
           int cost = edge.second;
           if (ans[next] > ans[now] + cost)
           {
               ans[next] = ans[now] + cost;
               if (!fv[next])
                   Q.push(next);
               fv[next] = 1;
               cnt[next] ++;
           }
       }
   }
   for (int i = 2; i <= n; ++ i)
       g << ans[i] << " ";

}