#include <fstream>
#include <limits>
#include <vector>
#include <queue>
 
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int INF = 0x3f3f3f3f;

int main()
{
    int n, m, a, b, c;
    fin>>n>>m;
    vector<vector<pair<int, int> > > adj(n, vector<pair<int, int> >());
    for (int i = 0; i < m; ++i) {
        fin>>a>>b>>c;
        adj[a-1].push_back(make_pair(b-1,c));
    }
    fin.close();

    vector<int> ret(n, INF);
    vector<bool> isInQueue(n, false);
    vector<int> noUpdated(n, 0);
    deque<int> dq;
    dq.push_back(0);
    ret[0] = 0;
    noUpdated[0] = 1;
    isInQueue[0] = true;
    while (dq.size()) { // for each node that was updated
        auto node = dq.front(); dq.pop_front();
        isInQueue[node] = false;
        if (noUpdated[node] >= n) {
            fout<< "Ciclu negativ!\n";
            return 0;
        }
        for (const auto& neigh : adj[node]) { // get edges and check if a new node is updating
            if (ret[node] < INF && ret[neigh.first] >  ret[node] + neigh.second) {
                ret[neigh.first] = ret[node] + neigh.second;
                if (!isInQueue[neigh.first]) {
                    dq.push_back(neigh.first);
                    isInQueue[neigh.second];
                    ++noUpdated[neigh.first];
                }
            }
        }
    }

    for (int i = 1; i < ret.size(); ++i) {
        fout<< ret[i] << " ";
    }

    fout.close();
    
    return 0;
}