#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define Nmax 50005
#define MAX 999999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector<pair<int,int> >Graph[Nmax];
vector<pair<int,int> >::iterator it;
queue<int>MY_QUEUE;
int Distance[Nmax];
int nr[Nmax];
int n;
void reading(int &n)
{
    int m,node1,node2,dist;
    f>>n>>m;
    while(m)
    {
         --m;
         f>>node1>>node2>>dist;
         Graph[node1].push_back(make_pair(node2,dist));
    }
    f.close();
}
void BELLMAN_FORD()
{
     int i,Node ;
     bool stop=false;
     for(i=1;i<=n;++i) {Distance[i]=MAX;nr[i]=0;}
     MY_QUEUE.push(1);Distance[1]=0;
     while(!MY_QUEUE.empty() && !stop)
     {
            Node=MY_QUEUE.front();
            MY_QUEUE.pop();

            for(it=Graph[Node].begin();it!=Graph[Node].end();++it)
            {
                if (Distance[it->first]>Distance[Node]+it->second)
                {
                    Distance[it->first]=Distance[Node]+it->second;
                    MY_QUEUE.push(it->first);
                    nr[it->first]=nr[it->first]+1;
                    if (nr[it->first]>n) stop=true;
                }
            }
     }
     if (stop) g<<"Ciclu negativ!";
     else
     for(i=2;i<=n;++i)
     g<<Distance[i]<<" ";
     g.close();
}
int main()
{
    reading(n);
    BELLMAN_FORD();
    return 0;
}