#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream F("bellmanford.in");
ofstream G("bellmanford.out");

int n, m, w[50003], c[50003], x, y, z, knod[50003];
queue <int> q;
vector <pair<int, int> > l[50003];
const int inf = 10000000;

int main()
{
    F >> n >> m;
    for(int i = 2; i <= n; ++ i)
        w[i] = inf;
    for(int i = 0; i < m; ++ i)
    {
        F >> x >> y >> z;
        l[x].push_back({y, z});
    }
    q.push(1);
    c[1] = 1;
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        c[x] = 0;
        for(vector< pair< int, int > >::iterator i = l[x].begin(); i != l[x].end(); ++ i)
        {
            if(w[(*i).first] > w[x] + (*i).second)
            {
                w[(*i).first] = w[x] + (*i).second;
                if(!c[(*i).first])
                    c[(*i).first] = 1, q.push((*i).first);
                if(++knod[(*i).first] > n)
                {
                    G << "Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for(int i = 2; i <= n; ++ i)
        G << w[i] << " ";
    return 0;
}