#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
#define inf 100000000
#define Nmax 50001
using namespace std;

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

vector<pair<int,int> >graf[Nmax];
queue<int>q;
bool viz[Nmax];
int drum[Nmax],n,m,nr[Nmax];

bool bellmanford() {
     int nod,distance,target,length ;
     while(!q.empty()) {

        nod=q.front();
        q.pop();
        viz[nod]=false;
        length=graf[nod].size();

        for(int i=0;i<length;i++) {

            target=graf[nod][i].first;
            distance=graf[nod][i].second;

            if(drum[target] > drum[nod]+distance) {

                drum[target]=drum[nod]+distance;
                if(!viz[nod]){

                    q.push(target);
                    viz[nod]=true;
                    nr[nod]++;
                    if(nr[nod]>n)
                        return false;
                }
            }
        }
     }
     return true;

}

int main()
{
    int node1,node2,dist;
    f>>n>>m;
    for(int i=1;i<=n;i++) {
        f>>node1>>node2>>dist;
        graf[node1].push_back(make_pair(node2,dist));
    }
    for(int i=2;i<=n;i++)
       drum[i]=inf;
    drum[1]=0;
    q.push(1);
    if(bellmanford()==false)
        g<<"Ciclu negativ!";
      else
        for(int i=2;i<=n;i++)
            g<<drum[i]<<" ";
    f.close();
    g.close();
    return 0;
}