#include <queue>
#include <fstream>
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

struct coord{
     int nod, cost;     
};

vector <coord> L[50009];
 
int n,m,viz[50009],S;
int d[50009];
 
void Citire()
{
    int x,y,i, c;
    coord w;
    fin >> n; // numarul de noduri
    fin >> m; // nr de muchii
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        w.nod = y; w.cost = c;
        L[x].push_back(w);
    }
}
 
void BFS(int k)
{      
    int i, j, c;
    queue<int> q;
    q.push(k);
    viz[k] = 1;
    while (!q.empty())
    {
        k = q.front();
        q.pop();
        for (j=0; j< L[k].size(); j++)
           {  i=L[k][j].nod; c=L[k][j].cost;
              if (!viz[i] || d[i] > d[k] + c)
              {  q.push(i);
                 d[i] = d[k] + c;
                 viz[i]++;
                 if (viz[i] > n) 
                 { fout << "Ciclu negativ!\n";
                   exit(0);
                 }
              }
        }
    }
}
  
void Afisare()
{
    int i, j;
    for (i=2; i<=n; i++)
      fout << d[i] << " ";
    fout << "\n";
}
 
int main ()
{
    int i;
    Citire();
    BFS(1);
    Afisare();
    fin.close();
    fout.close();
    return 0;
}