#include <iostream>
#include<fstream>
#include<vector>
#include<set>
#include<queue>

using namespace std;
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

#define nmax 50001
#define inf 1<<30

int n, m, i, a, b, x;
int cost[nmax], viz_nod[nmax];
bool viz[nmax];
vector<pair<int, int> > vecin[nmax];
set <pair <int, int> > s;

void bellmanford(){

    for(i=2; i<=n; i++) cost[i]=inf;

    s.insert(make_pair(0,1));

    while(!s.empty())
    {   int nod=(*s.begin()).second;
        int minim=(*s.begin()).first;

        s.erase(s.begin());

        viz[nod]=0;

    for(i=0; i<vecin[nod].size(); i++)
    {   int vc=vecin[nod][i].first;
        int c=vecin[nod][i].second;

        if(!viz[vc]) viz_nod[vc]++, viz[vc]=1;

        if(viz_nod[vc]>n){
            out<<"Ciclu negativ!";
            return ;
        }

        if (cost[vc]>minim + c){
            cost[vc]= minim +c;
        s.insert(make_pair(cost[vc], vc));
        }
        }
    }
    for(i=2; i<=n; i++)
        out<<cost[i]<<" ";
}

int main()
{
     in>>n>>m;
     for(i=1; i<=m; i++){
        in>>a>>b>>x;
        vecin[a].push_back(make_pair(b, x));
     }

     bellmanford();
    return 0;
}