#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <list>
#include <queue>
using namespace std;

#define inf 2000000

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

typedef pair <int, int> per;

vector < list<per> > graf;
list<per>::iterator it, last;
vector <bool> inCoada;
vector <int> aparitii, dist;

int n, m;

void citire(){
    int x, y, c;
    per aux;

    f >> n >> m;

    graf.resize(n+1);
    inCoada.resize(n+1);
    aparitii.resize(n+1);
    dist.resize(n+1, inf);

    for(int i = 1; i <= m; ++i){
        f >> x >> y >> c;
        aux.first = y; aux.second = c;
        graf[x].push_back(aux);
    }
    f.close();
}

int bellmanFord(){
    int top, nod, cost;
    queue<int> coada;
    dist[1] = 0;
    coada.push(1);

    while(!coada.empty()){
        top = coada.front();
        inCoada[top] = 0;
        coada.pop();
        ++aparitii[nod];
        if(aparitii[nod] >= n) return 0;

        it = graf[top].begin();
        last = graf[top].end();

        for(; it != last; ++it){
            nod = it->first; cost = it->second;

            if(dist[nod] > dist[top] + cost){
                dist[nod] = dist[top] + cost;
                if(!inCoada[nod])
                    inCoada[nod] = true, coada.push(nod);
            }
        }
    }

    for(int i = 2; i <= n; ++i)
        g << dist[i] << " ";
    return 1;
}

int main(){
    citire();
    if( !bellmanFord() ) g << "Ciclu negativ!\n";
    g.close();

    return 0;
}