#include <bits/stdc++.h>
#define DIM 2000001

using namespace std;

ifstream fin("bellmanford.in");

ofstream fout("bellmanford.out");

int i, x, y, c, n, m;

int dp[DIM], f[DIM], inQ[DIM];

vector < pair <int, int> > G[DIM];

void BellMan(){

    for(i=1;i<=n;i++)

        dp[i] = 1e9;

    dp[1] = 0;

    queue <int> Q;

    Q.push(1);

    inQ[1] = 1;

    while(!Q.empty()){

        int node = Q.front();

        inQ[node] = false;

        Q.pop();

        for(auto k : G[node]){

            if(dp[node] + k.second < dp[k.first]){

                dp[k.first] = dp[node] + k.second;

                if(!inQ[k.first]){

                    Q.push(k.first);

                    f[k.first] ++;

                    if(f[k.first] >= 2000){

                        fout << "Ciclu negativ!";

                        exit(0);

                    }

                }

            }

        }


    }


}
int main(){

    fin >> n >> m;

    while(m--){

        fin >> x >> y >> c;

        G[x].push_back(make_pair(y, c));


    }

    BellMan();

    for(i=2;i<=n;i++)

        fout << dp[i] << " ";

}