#include<bits/stdc++.h>
using namespace std;

const int N_MAX = 50005;
const int oo = 0x3f3f3f3f;

ofstream g("bellmanford.out");

typedef pair<int, int> Edge;

vector<Edge>G[N_MAX];
bitset<N_MAX>visited;
queue<int> Q;

int dist[N_MAX], inQ[N_MAX];
int N, M;

void read()
{
    ifstream f("bellmanford.in");

    f >> N >> M;

    while(M --)
    {
        int x, y, c;
        f >> x >> y >> c;
        G[x].emplace_back(y, c);
    }

    f.close();
}

void solve()
{
    bool visited[N_MAX];
    int start_point = 1;

    memset(dist, oo, sizeof(dist));
    memset(visited, false, sizeof(visited));

    dist[start_point] = 0;
    visited[start_point] = true;
    Q.push(start_point);
    inQ[start_point] ++;

    while(!Q.empty())
    {
        int node = Q.front();
        Q.pop();
        visited[node] = false;

        for(const auto &son : G[node]){
            int to = son.first;
            int newCost = son.second;
            if( dist[to] > dist[node] + newCost ){
                dist[to] = dist[node] + newCost;
                if( !visited[to] ){
                    visited[to] = true;
                    inQ[to] ++;
                    Q.push(to);
                    if( inQ[to] > N ){
                        g << "Ciclu negativ!";
                        break;
                    }
                }
            }
        }
    }

    for(int i = 2; i <= N; i ++){
        if( dist[i] == oo ) dist[i] = 0;
        g << dist[i] <<" ";
    }
}

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