#include <fstream>
#include <vector>
#include <queue>
#define oo 0x3f3f3f3f

using namespace std;

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

typedef pair <int, int> PER;

vector <PER> G[50001];

int D[50001],P[50001],nr[500001];
bool V[50001];

int main()
{
int N, m;
fin >> N >> m;
for(int i = 1; i <= m; ++i)
    {
int x, y, c;
fin >> x >> y >> c;
G[x].push_back(make_pair(y, c));
    }

for(int i = 0; i <= N; i++)
    {
      D[i] = oo;
      P[i] = 0;
      V[i] = false;}
      V[1] = true;
      D[1] = 0;
      queue<int>Q;
      Q.push(1);
      while(!Q.empty())
          {
            int nod = Q.front();
            V[nod] = false;
            vector<PER>::iterator i;
            for(i = G[nod].begin(); i != G[nod].end(); ++i)
            if (D[nod]+i->second < D[i->first])
                {
                    D[i->first] = D[nod] + i->second;
                    if(!V[i->first])
                    {
                        if(nr[i->first] > N)
                        {
                            fout<<"Ciclu negativ!\n";
                            return 0;
                        }
                        Q.push(i->first);
                        V[i->first]=true;
                        ++nr[i->first];
                    }
                }
            Q.pop();
         }
      for(int i = 2; i <= N; i++)
      fout << D[i] << " ";
return 0;
}