#include <bits/stdc++.h>
const long long INF = INT_MAX;
std::ifstream fin("bellmanford.in");
std::ofstream fout("bellmanford.out");
int main(){
    //memorarea e la fel ca la dijkstra
    // dist[i]=INF
    // dist[start]=0;
    // cnt[i] = 0;
    // ind[start=s]=1;
    // pq.push(s);
    // cnt[s]=1
    /*/
        while(!pq.empty()){
        int nod=pq.top();
        pq.pop();
        ind[nod]=0;
        for v in l[nod]
            vecin v.first  
            cost = v.second
            if(d[vecin] > d[nod] + cost)
                d[vecin]= d[nod]+cost
                if(vecin in coada (cu ind[vecin])) continue
                else {
                pq.push(vecin)
                ind[vecin]=1
                if(++cnt[vecin]>n) print CICLU NEGATIV return0;
                
        }
    */
   int n,m;
    if(!(fin>>n>>m)) return 0;
    std::vector<std::vector<std::pair<int,int>>> L(n+1);
    for(int i=0;i<m;i++){
        int n1,n2,w;
        fin>>n1>>n2>>w;
        L[n1].push_back({n2,w});
    }

    const long long INF = INT_MAX;
    std::vector<long long> dist(n+1, INF);
    dist[1] = 0;
    
    std::vector<bool> in_pq(n+1,false);
    std::vector<int> cnt(n+1,0);
    in_pq[1]=true;
    cnt[1]=1;
    std::queue<int> q;
    q.push(1);
    while(!q.empty()){
        auto nod=q.front();
        q.pop();
        in_pq[nod]=false;
        for(auto &x : L[nod]){
            int vecin= x.first;
            int cost = x.second;
            if(dist[vecin] > dist[nod]+cost){
                dist[vecin] = dist[nod]+cost;
                if(in_pq[vecin]) continue;
                else{
                    q.push(vecin);
                    in_pq[vecin]=true;
                    if(++cnt[vecin]>n) {
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for(int i=2;i<=n;i++){
        if(dist[i]==INF) fout << 0;
        else fout << dist[i];
        if(i<n) fout << ' ';
    }

    fin.close();
    fout.close();
    return 0;
}