#include<cstdio>
    #include<fstream>
    #include<vector>
    #include<set>

    #define MAX 50001
    #define pb push_back
    #define INF 50000002
    using namespace std;
    int N,M,d[MAX] , viz[MAX];
    bool inq[MAX];
    vector<int> G[MAX] ,C[MAX];
    vector<int>::iterator it,it1;
    struct Comp{
    bool operator()(int i,int j)
    {
        return d[i] < d[j];
    }
    };
    multiset<int,Comp> Q;

    void citire();
    bool bellmanford(int sursa);
    void tipar();

    int main()
    {
        citire();
        tipar();
        return 0;
    }

    void citire()
    {
        int x , y , c;
        ifstream f("bellmanford.in");
        f>>N>>M;
        for( int i = 1 ; i <= M ; ++i )
        {
            f>>x>>y>>c;
            G[x].pb(y);C[x].pb(c);
        }
        f.close();
    }

    bool bellmanford(int sursa)
    {
        int k ;
        for( int i = 1 ; i <= N ; ++i )d[i] = INF;
        d[sursa] = 0;
        Q.insert(sursa);inq[sursa] = 1;
        while(!Q.empty())
        {
            k = *Q.begin();
            Q.erase(Q.begin());
            for( it = G[k].begin() , it1 = C[k].begin() ; it < G[k].end() ;  it++ , it1++)
                if(d[*it] > d[k]+ *it1)
                {
                    d[*it] = d[k] + *it1;
                    Q.insert(*it);
                    if(++viz[*it] >= N)
                    return false;
                }
        }
        return true;
    }

    void tipar()
    {
        ofstream g("bellmanford.out");
        if(bellmanford(1))
            for( int i = 2 ; i <= N ; ++i )
                if(d[i] ==INF)
                    g<<"0"<<" ";
                else
                    g<<d[i]<<" ";
        else
            g<<"Ciclu negativ!";
        g.close();
    }