#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
using namespace std;

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

bool cond=1;
const int INF = 2000000000;
const int NMAX = 50001;

int N, M;

vector < pair < int, int > > Ad[NMAX];

queue < pair < int, int > > H;

int vis[NMAX];
int dist[NMAX];

void Dijkstra( int nod ){
    bool inq[NMAX]={0};
    H.push(make_pair(0,nod));

    for( int i = 1; i <= N; ++i )
        if( i != nod )
            dist[i] = INF;
    while( !H.empty() ){

        int nod = H.front().second;
        int cost = H.front().first;
        H.pop();
        inq[nod]=0;
        for( int i = 0; i < Ad[nod].size(); ++i ){
            pair < int , int > w = Ad[nod][i];
            if( dist[w.second] > dist[nod] + w.first ){
                dist[w.second] = dist[nod] + w.first;
                if(inq[w.second]==0)H.push( make_pair(dist[w.second], w.second )),inq[w.second]=1;
                vis[w.second]++;
                if(vis[w.second]>=N)
                {
                    fout << "Ciclu negativ!";
                    cond = 0;
                    return;
                }
            }
        }
    }
}
int main()
{
    fin >> N >> M;

    int x, y, c;
    for( int i = 1; i <= M; ++i ){
        fin >> x >> y >> c;
        Ad[x].push_back( make_pair(c,y) );
    }
    Dijkstra(1);

    for( int i = 2; i <= N && cond; ++i)
        fout << dist[i] << ' ';
    fout << '\n';
    return 0;
}