#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];

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

void BellMan(){

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

        dp[i] = 1e9;

    dp[1] = 0;

    bool can_improve = 1;

    while(can_improve){

        can_improve = 0;

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

            for(auto k : G[i])

                if(dp[i] != 1e9 && dp[i] + k.second < dp[k.first]){

                    can_improve = 1;

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

                    f[k.first]++;

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

                        fout << "Ciclu negativ!";

                        exit(0);

                    }

                }


    }


}
int main(){

    fin >> n >> m;

    while(m--){

        fin >> x >> y >> c;

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

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


    }

    BellMan();

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

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

}