#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 50005;
const int INF = 1e9;

struct Muchie{
    int to, cost;
};

vector <Muchie> g[NMAX];

int n;
int dist[NMAX];
int cnt[NMAX];
bool viz[NMAX];

void bellmanford(){
    for(int i = 1; i <= n; ++i){
        dist[i] = INF;
    }
    queue <int> pq;
    pq.push(1);
    dist[1] = 0;
    //viz[1] = 1;
    cnt[1] = 1;
    while(!pq.empty()){
        int from = pq.front();
        pq.pop();
        //viz[from] = 0;
        for(auto e: g[from]){
            int nod = e.to;
            int cost = e.cost;
            if(dist[nod] > dist[from] + cost){
                dist[nod] = dist[from] + cost;
                //if(viz[nod] == 0){
                    //viz[nod] = 1;
                    cnt[nod] ++;
                    pq.push(nod);
                    if(cnt[nod] > n){
                        fout << "Ciclu negativ!";
                        fout.close();
                        return;
                    }
                //}
            }
        }
    }
}

void solve(){
    int m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        Muchie temp;
        temp.to = y;
        temp.cost = c;
        g[x].push_back(temp);
    }
    bellmanford();
    for(int i = 2; i <= n; ++i){
        fout << dist[i] << " ";
    }
}

int main()
{
    solve();
    return 0;
}