#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("bellmanford.in");
ofstream fout("bellmanford.out");

const int INF = 2000000000;
const int NMAX = 50001;

int N, M;

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

priority_queue < pair < int, int > > H;

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

void Dijkstra( int nod ){
    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.top().second;
        int cost = H.top().first;
        H.pop();
        vis[nod]++;
        if(vis[nod]>N)
        {
            fout << "Ciclu negativ!";
            return;
        }
        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;
                H.push( make_pair(dist[w.second], w.second ));
            }
        }
    }
}
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; ++i)
        fout << dist[i] << ' ';
    fout << '\n';
    return 0;
}